Cod sursa(job #600941)

Utilizator Smaug-Andrei C. Smaug- Data 4 iulie 2011 13:35:21
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>

#define MAXN 30005

int A[MAXN], B[MAXN], N, L, U, D[MAXN];
double S[MAXN];

int check(double v){
  
  int l, r, i;

  S[0]=0;
  for(i=1; i<=N; i++)
    S[i]=((double)A[i])-((double)B[i])*v;

  l=1; r=0;
  for(i=L+1; i<=N; i++){
    if(l<=r && i-D[l]>U)
      l++;
    while(l<=r && S[D[r]]>=S[i-L])
      r--;

    D[++r]=i-L;

    if(l<=r && S[D[l]]<=S[i])
      return 1;
  }

  return 0;

}

int main(){

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

  int i;
  double l, r, mid;

  scanf("%d%d%d", &N, &L, &U);
  A[0]=B[0]=0;
  for(i=1; i<=N; i++){
    scanf("%d", A+i);
    A[i]=A[i]+A[i-1];
  }
  for(i=1; i<=N; i++){
    scanf("%d", B+i);
    B[i]=B[i]+B[i-1];
  }
  
  l=0; r=1000.00;

  while(l<=r){
    mid=((r-l)/2)+l;
    if(check(mid))
      l=mid+0.01;
    else
      r=mid-0.01;
  }
  
  printf("%.2lf\n", r);

  return 0;

}