Cod sursa(job #169423)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 1 aprilie 2008 18:05:05
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
int n,l,u,i,r,c[30003],t[30003],ls,ld,a[30003],q[30003],rr;
long long smax,s[30003];
void secv(){
     int lo=1,hi=l,p,j,prim=1,ult=1;
     q[1]=1;
     for (i=l+1;i<=n;i++){
         while (i-q[prim]+1>u) prim++;
         j=ult;
         while (j>=prim && (s[i]-s[q[j]-1]<s[i]-s[i-l])) j--;
         q[++j]=i-l+1;ult=j; 
         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(){
    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) ls=r+1;
           else  ld=r-1;
          }
    printf("%d.",r/100);
    r=r%100;
    if (r<10) printf("0%d",r);
          else printf("%d",r);
    return 0;
     }