Pagini recente » Cod sursa (job #3176348) | Cod sursa (job #3001017) | Cod sursa (job #2898329) | Cod sursa (job #942677) | Cod sursa (job #347261)
Cod sursa(job #347261)
#include <stdio.h>
#define Nmax 30005
#define ll long long
int c[Nmax],t[Nmax];
int n,i,U,L,st,dr,x,sol,p,u;
int q[Nmax];
ll s[Nmax],a[Nmax],max,aux;
int main(){
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]),c[i]*=100;
for(i=1;i<=n;++i) scanf("%d",&t[i]);
st=0; dr=100000; s[0]=0;
while( st<=dr ){
x=st+(dr-st)/2;
for(i=1;i<=n;++i){
a[i]=c[i]-t[i]*x;
s[i]=s[i-1]+a[i];
}
max=s[L];
p=u=1; q[1]=1; // deque
for(i=L+1; i<=n; ++i){
if(i-q[p]+1 > U) p++;
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, st=x+1;
else dr=x-1;
}
printf("%d.",sol/100);
sol %=100;
if(sol<10) printf("0");
printf("%d",sol);
fclose(stdin); fclose(stdout);
return 0;
}