Pagini recente » Cod sursa (job #1916821) | Cod sursa (job #2555275) | Cod sursa (job #248457) | Cod sursa (job #940429) | Cod sursa (job #1391474)
#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;i++){
while(jj>=ii && s[ c[jj] ]>=s[i])
jj--;
c[++jj]=i;
while(ii<=jj && i-c[ii]>p)
ii++;
if(i-c[ii]>=l && sm< s[i]-s[ c[ii] ])
sm=s[i]-s[ c[ii] ];
}
return sm;
}
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 afis()
{
FILE *g;
g=fopen("secv3.out","w");
fprintf(g,"%.2f",(double)(sol)/100);
fclose(g);
}
int main()
{
READ();
caut_binar();
afis();
return 0;
}