Cod sursa(job #188511)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 8 mai 2008 19:51:19
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
int n,l,u,i,r,c[30003],t[30003],ls,ld,a[30003],q[30003];
long long smax,s[30003];
void secv(){
     int lo=1,hi=l,p,prim=1,ult=1;
     q[1]=1;
     for (i=l+1;i<=n;i++){
         while (prim<=ult && (i-q[prim]+1>u)) prim++;
         while (prim<=ult && (s[hi]-s[lo-1]>=s[i]-s[q[prim]-1])) prim++;
         while (ult>=prim && ((s[i]-s[q[ult]-1])<(s[i]-s[i-l]))) ult--;
         q[++ult]=i-l+1; 
         p=q[prim];
         if (s[hi]-s[lo-1]<s[i]-s[p-1]) {lo=p;
                                         hi=i;}
         }
     smax=s[hi]-s[lo-1];
     }
int main(){
    int aux;
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d %d %d",&n,&l,&u);
    for (i=1;i<=n;i++) scanf("%d",&c[i]);
    for (i=1;i<=n;i++) scanf("%d",&t[i]);
    for (i=1;i<=n;i++) c[i]*=100;
    ls=0;ld=100001;s[0]=0;
    while (ls<=ld){
          r=(ls+ld)/2;
          for (i=1;i<=n;i++) a[i]=c[i]-r*t[i];
          for (i=1;i<=n;i++) s[i]=s[i-1]+a[i];
          secv();
          if (smax<0.01) aux=r;
          if (smax>=0) ls=r+1;
           else  ld=r-1;
          }
    r=aux;
    printf("%d.",r/100);
    r=r%100;
    if (r<10) printf("0%d",r);
          else printf("%d",r);
    return 0;
     }