Cod sursa(job #188549)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 8 mai 2008 21:19:05
Problema Secventa 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
const int NMAX=30001;
int n,ul,l,c[NMAX],t[NMAX];
int main(){
    int ls,ld,x,i,a[NMAX],s[NMAX],p,u,max,q[NMAX],sol;
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d %d %d",&n,&l,&ul);
    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=100000;s[0]=0;
    while (ls<=ld){
          x=(ls+ld)/2;
          for (i=1;i<=n;++i) a[i]=c[i]-x*t[i];
          for (i=1;i<=n;++i) s[i]=s[i-1]+a[i];
          max=s[l];
          p=u=1;q[1]=1;
          for (i=l+1;i<=n;++i){
              if (i-q[p]+1>ul) p++;
              int aux=s[i]-s[i-l];
              while (aux>s[i]-s[q[u]-1] && u>=p) --u;
              q[++u]=i-l+1;
              aux=s[i]-s[q[p]-1];
              if (aux>max) max=aux;
              }
          if (max>=0) {sol=x;
                       ls=x+1;}
                 else ld=x-1;
          }
    printf("%d.",sol/100);
    sol%=100;
    if (sol<10) printf("0");
    printf("%d",sol);
    return 0;
     }