Pagini recente » Cod sursa (job #1016128) | Cod sursa (job #2114037) | Cod sursa (job #2112043) | Cod sursa (job #818044) | Cod sursa (job #359659)
Cod sursa(job #359659)
#include <stdio.h>
#include <algorithm>
int a[30100], b[30100], deque[30100];
long long s[30100];
int st,dr,i,n,mij,l,u;
float sol;
bool ok(int x)
{
int i,j,st,dr;
s[0]=0; deque[0]=0; st=1; dr=0;
for (i=1; i<=n; i++){
s[i]=(long long)s[i-1]+a[i]-b[i]*x;
if (i>=l){
while (st<=dr && s[deque[dr]]>s[i-l]){
deque[dr]=0;
dr--;
}
deque[++dr]=i-l;
if (deque[st]<i-u){
deque[st]=0;
st++;
}
if (s[deque[st]]<=s[i]){
for (j=st; j<=dr; j++)
deque[j]=0;
return true;
}
}
}
for (i=st; i<=dr; i++)
deque[i]=0;
return false;
}
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",&a[i]);
a[i]=a[i]*100;
if (dr<a[i])
dr=a[i];
}
for (i=1; i<=n; i++)
scanf("%d",&b[i]);
st=0;
while (st<=dr){
mij=(st+dr)/2;
if (ok(mij)){
sol=mij;
st=mij+1;
}
else
dr=mij-1;
}
sol=sol/100;
printf("%.2f\n",sol);
return 0;
}