Cod sursa(job #28032)

Utilizator t30Rosu Teodor t30 Data 7 martie 2007 14:03:10
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#define MAX 100000
int n,l,p,a[30010],b[30010];
long d[30010],s[30010],ss,sm,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;
   for(i=1;i<=n;i++)
      d[i]=a[i]*100-b[i]*k;

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

   ii=1;jj=l; ss=s[jj]-s[ii-1]; sm=ss;

   for(jj=l+1;jj<=n;jj++){ ss+=d[jj];
	if(jj-ii>=p) { ii++; ss-=d[ii-1]; }
	if(ss< s[jj]-s[jj-l]) { ii=jj-l+1; ss=s[jj]-s[jj-l]; }
	if(ss>sm) sm=ss;
   }

   while(jj-ii+1>l) { ii++; ss-=d[ii-1]; if(ss>sm) ss=sm; }


   return sm;
}


void SEARCH()
{  long p;
   for(p=1;p<2*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/100);
   fclose(g);
}

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