Cod sursa(job #1037532)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 20 noiembrie 2013 12:46:48
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>

#include <algorithm>
#include <vector>

using namespace std;

double g[30005];
int ct[30005], tp[30005], dq[30005];

int main(){
  freopen("secv3.in", "r", stdin);
  freopen("secv3.out", "w", stdout);

  int n, l, u;
  scanf("%d%d%d", &n, &l, &u);

  for(int i = 1; i <= n; ++i)
    scanf("%d", &ct[i]);

  for(int i = 1; i <= n; ++i)
    scanf("%d", &tp[i]);

  double left = 0.0, right = 13371337.133742, mid, ans = 0.0;
  for(int pas = 1; pas <= 137; ++pas){
    if(right - left < 1e-5)
      break;
    mid = (left + right) / 2;

    for(int i = 1; i <= n; ++i)
      g[i] = g[i - 1] + (double)ct[i] - mid * (double)tp[i];

    int lef = 0, rai = 0, isk = 0;
    dq[lef] = 0;
    for(int i = 1; i <= n; ++i){
      if(i - l > 0){
        dq[++rai] = i - l;
        while(rai > lef && g[dq[rai]] < g[dq[rai - 1]]){
          dq[rai - 1] = dq[rai];
          --rai;
        }
      }
      while(i - dq[lef] > u && lef <= rai){
        ++lef;
      }
      if(g[i] - g[dq[lef]] >= 0.0)
        isk = 1;
    }

    if(isk){
      ans = mid;
      left = mid;
    }
    else
      right = mid;
  }

  printf("%lf", ans);

  return 0;
}