Pagini recente » Borderou de evaluare (job #179518) | Cod sursa (job #2445408)
#include<fstream>
#include<deque>
using namespace std;
ifstream cin("secv3.in");
ofstream cout("secv3.out");
int n,l,u,sol;
long long c[30005],t[30005],r[30005];
deque<int> d;
int begin,end,middle;
long long ans(int x){
long long Max=-3e14;
for(int i=1;i<=n;i++)
r[i]=c[i]-t[i]*x;
for(int i=l;i<=n;i++){
while(!d.empty() && r[d.back()]>r[i-l]) d.pop_back();
d.push_back(i-l);
Max=max(Max,r[i]-r[d.front()]);
if(d.front()==i-u) d.pop_front();
}
d.clear();
return Max;
}
int main(){
cin>>n>>l>>u;
for(int i=1;i<=n;i++) {int x; cin>>x; c[i]=c[i-1]+100*x;}
for(int i=1;i<=n;i++) {int x; cin>>x; t[i]=t[i-1]+x;}
begin=0; end=100000;
while(end-begin>1){
middle=(begin+end)/2;
if(ans(middle)>=0){
sol=middle;
begin=middle;
}
else end=middle;
}
cout<<sol/100.0;
}