Cod sursa(job #886607)

Utilizator stoicatheoFlirk Navok stoicatheo Data 23 februarie 2013 00:19:12
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>
#define MAX 100001
int n,l,p,a[30010],b[30010],c[30010];
long long d[30010],s[30010],sol;

void READ()
{
   int i;

   FILE *f;
   f=fopen("secv3.in","r");
   fscanf(f,"%d %d %d",&n,&l,&p);
   for(i=1;i<=n;i++)
    fscanf(f,"%d",&a[i]);
   for(i=1;i<=n;i++)
    fscanf(f,"%d",&b[i]);
   fclose(f);
}

long long ok(long long k)
{
   int i,ii,jj;
   long long sm;
   for(i=1;i<=n;i++)
      d[i]=100*(long long )a[i]-k*b[i];

   s[0]=0;
   for(i=1;i<=n;i++)
    s[i]=s[i-1]+d[i];

   sm=0;
   for(i=1;i<=l;i++)
    sm=sm+d[i];

   c[0]=0; ii=0; jj=0;
   for(i=1;i<=n-l;i++){

    while(jj>=ii && s[ c[jj] ]>=s[i]) jj--;
       c[++jj]=i;

       while(ii<=jj && i-c[ii]>p-l) ii++;

       if(ii<=jj && sm< s[i+l]-s[ c[ii] ]) sm=s[i+l]-s[ c[ii] ];
   }


  return sm;

}




void SEARCH()
{  long long p;
   for(p=1;p<MAX;p<<=1);
   for(sol=0;p;p>>=1)
    if(sol+p<=MAX && ok(sol+p)>=0) sol=sol+p;

}

void PRINT()
{
   FILE *g;
   g=fopen("secv3.out","w");
   fprintf(g,"%.2f",(double)(sol)/100);
   fclose(g);
}


int main()
{
   READ();
   SEARCH();
   PRINT();
return 0;
}