Pagini recente » Cod sursa (job #2059648) | Cod sursa (job #189958) | Cod sursa (job #1225048) | Cod sursa (job #63884) | Cod sursa (job #188554)
Cod sursa(job #188554)
#include <cstdio>
const int NMAX=30001;
int n,U,L,c[NMAX],t[NMAX];
long long s[NMAX],a[NMAX];
int main(){
int ls,ld,x,i,p,u,max,q[NMAX],sol;
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d %d %d",&n,&L,&U);
for (i=1;i<=n;++i) scanf("%d",&c[i]);
for (i=1;i<=n;++i) scanf("%d",&t[i]);
for (i=1;i<=n;++i) c[i]*=100;
ls=0;ld=100000;s[0]=0;
while (ls<=ld){
x=(ls+ld)/2;
for (i=1;i<=n;++i) a[i]=c[i]-x*t[i];
for (i=1;i<=n;++i) s[i]=s[i-1]+a[i];
max=s[L];
p=u=1;q[1]=1;
for (i=L+1;i<=n;++i){
if (i-q[p]+1>U) p++;
int aux=s[i]-s[i-L];
while (aux>s[i]-s[q[u]-1] && u>=p) --u;
q[++u]=i-L+1;
aux=s[i]-s[q[p]-1];
if (aux>max) max=aux;
}
if (max>=0) {sol=x;
ls=x+1;}
else ld=x-1;
}
printf("%d.",sol/100);
sol%=100;
if (sol<10) printf("0");
printf("%d",sol);
return 0;
}