Cod sursa(job #1391465)

Utilizator dorupopDoru Pop dorupop Data 17 martie 2015 23:01:00
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 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 caut_binar()
{
    long long st=0, dr=3000000000;
    while(st<=dr){
        long long mij=(st+dr)/2;
        if(ok(mij)>=0){
            sol=mij;
            st=mij+1;

        }
        else
            dr=mij-1;

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


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