Cod sursa(job #944467)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 28 aprilie 2013 17:45:00
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>

using namespace std;

int nums[50005], fr[50005], dq[50005];
double nw[50005], sp[50005];

int main(){
  ifstream in("secv3.in");
  ofstream out("secv3.out");

  int n, l, u;
  in >> n >> l >> u;

  for(int i = 1; i <= n; ++i)
    in >> nums[i];
  for(int i = 1; i <= n; ++i)
    in >> fr[i];

  double left = 0.0, right = 1e8, ans = 0.0, mid;
  for(int i = 1; i <= 400; ++i){
    mid = (left + right) / 2.0;

    for(int j = 1; j <= n; ++j)
      nw[j] = (double)nums[j] - (double) fr[j] * mid;

    for(int j = n; j > 0; --j)
      sp[j]  = nw[j] + sp[j + 1];

    int rit = l + 1, sz = 0, rt =  0, ok = 0;
    for(int j = 1; j <= n - l + 1; ++j){
      while(sz && dq[rt - sz + 1] < j + l)
        --sz;
      while(rit <= n && rit <= j + u){
        dq[++rt] = rit;
        while(sz > 1 && sp[dq[rt]] < sp[dq[rt - 1]]){
          dq[rt - 1] = dq[rt];
          --sz;
          --rt;
        }
        ++rit;
      }
      if(sp[j] - sp[dq[rt - sz + 1]] >= 0)
        ok = 1;
    }

    if(ok){
      left = mid;
    }
    else
      right = mid;
  }

  out << mid;

  return 0;
}