Pagini recente » Cod sursa (job #2598763) | Cod sursa (job #579183) | Cod sursa (job #2156065) | Cod sursa (job #495359) | Cod sursa (job #886607)
Cod sursa(job #886607)
#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;
}