Cod sursa(job #1607726)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 21 februarie 2016 15:55:29
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <iomanip>

#include <iostream>

using namespace std;

const int MAX_N = 30000;

int S[2][MAX_N + 1];
int D[MAX_N];

int main() {
  ifstream fin("secventa3.in");
  ofstream fout("secventa3.out");
  fin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, L, U; fin >> N >> L >> U;

  for (int i = 0; i <= 1; ++ i) {
    for (int j = 1; j <= N; ++ j) {
      fin >> S[i][j]; S[i][j] += S[i][j - 1];
    }
  }
  fin.close();

  double st = .0, fn = 3e7 + 1, mid;

  while (fn - st > 1e-4) {
    mid = st + (fn - st) * 0.5;
    
    int lo = 0, hi = 0;

    bool pass = false;

    int i = L;

    do {
      const double curr = S[0][i - L] - mid * S[1][i - L];

      while (lo != hi && S[0][D[hi - 1]] - mid * S[1][D[hi - 1]] > curr) {
	hi--;

	if (hi == -1) {
	  hi = N - 1;
	}
      }
      
      D[hi++] = i - L;

      if (hi == N) {
	hi = 0;
      }

      if (D[lo] < i - U) {
	lo++;

	if (lo == N) {
	  lo = 0;
	}
      }
      
      pass |= (S[0][i] - mid * S[1][i] >= S[0][D[lo]] - mid * S[1][D[lo]]);

    } while (++ i <= N && !pass);

    if (pass) {
      st = mid;
    } else {
      fn = mid;
    }
  }

  fout << fixed << setprecision(2) << st << '\n';
  fout.close();
  return 0;
}