Pagini recente » Cod sursa (job #3250125) | Cod sursa (job #3183388) | Cod sursa (job #3236466) | Cod sursa (job #28965) | Cod sursa (job #28959)
Cod sursa(job #28959)
#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+1]-s[i];
while(ii<=jj && i-c[ii]+1>p-l) ii++;
while(jj>=ii && s[i]- s[ c[jj]-1 ]<d[i]) jj--;
c[++jj]=i;
if(sm< s[i+l]-s[ c[ii]-1 ]) sm=s[i]-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/100);
fclose(g);
}
int main()
{
READ();
SEARCH();
PRINT();
return 0;
}