Pagini recente » Borderou de evaluare (job #2005640) | Cod sursa (job #2006535) | Cod sursa (job #2297303) | Cod sursa (job #3337857) | Cod sursa (job #3315150)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4;
const double eps=0.00001;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int n,l,u;
double c[MAXN+1],t[MAXN+1];
bool check(double x) {
vector<double>pfx(n+1,0);
for(int i=1; i<=n; i++) {
pfx[i]=pfx[i-1]+c[i]-x*t[i];
}
deque<int>dq;
double res=0;
for(int i=l; i<=n; i++) {
while(!dq.empty()&&pfx[dq.back()]>=pfx[i-l+1]) {
dq.pop_back();
}
dq.push_back(i-l);
if(!dq.empty()) {
res=max(res,pfx[i]-pfx[dq.front()]);
}
if(!dq.empty()&&dq.front()<i-u) {
dq.pop_front();
}
}
return res>0;
}
int main() {
fin>>n>>l>>u;
for(int i=1; i<=n; i++) {
fin>>c[i];
}
for(int i=1; i<=n; i++) {
fin>>t[i];
}
double l=0,r=1e9;
while(r-l>=eps) {
double mid=(l+r)/2;
if(check(mid)) {
l=mid;
} else {
r=mid;
}
}
fout<<fixed<<setprecision(2)<<l;
return 0;
}