Pagini recente » Cod sursa (job #520559) | Cod sursa (job #594346) | Cod sursa (job #1949611) | Cod sursa (job #2566783) | Cod sursa (job #246384)
Cod sursa(job #246384)
#include <cstdio>
#define x 100
#define lm 30001
long t[lm],c[lm],n,i,r,l,u;
long long v[lm],s[lm];
bool smax(long k)
{
long i,d,j,a[lm],p[lm],st,dr;
long long q[lm],sm,b;
d=u-l+1;
for (i=1; i<=n; i++) a[i]=c[i]-(k*t[i]);
for (i=1; i<=n; i++) s[i]=s[i-1]+a[i];
st=1;
dr=1;
q[1]=a[1];
p[1]=1;
v[1]=a[1];
for (i=2; i<=n; i++)
{
while (p[st]+d<i) st++;
v[i]=s[i]-q[st];
while ((s[i]<=q[dr])&(dr>=st)) dr--;
dr++;
q[dr]=s[i];
p[dr]=i;
}
sm=-1;
for (i=l; i<=n; i++)
{
b=0;
b=s[i]-s[i-l+1];
b+=v[i-l+1];
if (b>sm) sm=b;
}
if (sm>-1) sm=1; else sm=0;
return sm;
}
long caut(long a, long b)
{
long k,r;
while (a<=b)
{
k=(a+b)/2;
if (smax(k))
{
r=k;
a=k+1;
} else b=k-1;
}
return r;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%ld %ld %ld",&n,&l,&u);
for (i=1; i<=n; i++)
{
scanf("%ld",&c[i]);
c[i]*=x;
}
for (i=1; i<=n; i++) scanf("%ld",&t[i]);
r=caut(1,30000000);
printf("%ld.",r/x);
if (r%x<10) printf("0");
printf("%ld\n",r%x);
// smax(50);
}