Cod sursa(job #29068)

Utilizator t30Rosu Teodor t30 Data 8 martie 2007 16:29:52
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
#define MAX 100000
int n,l,p,a[30010],b[30010],c[30010];
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 ok(long k)
{
   int i,ii,jj;
   long sm;
   for(i=1;i<=n;i++)
      d[i]=100*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]=1; ii=0; jj=-1;

   for(i=1;i<=n-l;i++){
       if(s[i+l]-s[i]>sm) sm=s[i+l]-s[i];

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

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

}


void SEARCH()
{  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",(float)(sol+1)/100);
   fclose(g);
}


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