Pagini recente » Cod sursa (job #1170495) | Cod sursa (job #586415) | Cod sursa (job #2325218) | Cod sursa (job #754546) | Cod sursa (job #804214)
Cod sursa(job #804214)
#include<cstdio>
#include<cmath>
#include<deque>
#include<algorithm>
using std::max;
using std::deque;
int t[30005];
int c[30005];
int v[30005];
int n,l,u;
bool isok (int m)
{
for(int i=0;i<n;i++)
v[i]=v[i-1]+c[i]*100-t[i]*m;
deque<int> d;
if(v[l]>=0)
return true;
else{
for(int i=l;i<n;i++){
while(d.empty()==false&&v[d.back()]>v[i-l])
d.pop_back();
d.push_back (i-l);
while(d.front()<=i-u-1)
d.pop_front();
if(v[i]-v[d.front()]>=0){
return true;
}
}
}
return false;
}
int main()
{
freopen ("secv3.in","r",stdin);
freopen ("secv3.out","w",stdout);
scanf ("%d%d%d",&n,&l,&u);
scanf ("%d",c);
for(int i=1;i<n;i++){
scanf ("%d",c+i);
// c[i]+=c[i-1];
}
scanf ("%d",t);
for(int i=1;i<n;i++){
scanf ("%d",t+i);
// t[i]+=t[i-1];
}
long long s=1,e=1000000LL*100+5;
while(s<e){
long long m=(s+e)/2;
if(m==s)
m=e;
if(isok (m))
s=m;
else
e=m-1;
}
printf ("%lld.%02lld",s/100,s%100);
return 0;
}