Pagini recente » Cod sursa (job #2178279) | Cod sursa (job #2920582) | Cod sursa (job #2698259) | Cod sursa (job #2548355) | Cod sursa (job #944467)
Cod sursa(job #944467)
#include<fstream>
using namespace std;
int nums[50005], fr[50005], dq[50005];
double nw[50005], sp[50005];
int main(){
ifstream in("secv3.in");
ofstream out("secv3.out");
int n, l, u;
in >> n >> l >> u;
for(int i = 1; i <= n; ++i)
in >> nums[i];
for(int i = 1; i <= n; ++i)
in >> fr[i];
double left = 0.0, right = 1e8, ans = 0.0, mid;
for(int i = 1; i <= 400; ++i){
mid = (left + right) / 2.0;
for(int j = 1; j <= n; ++j)
nw[j] = (double)nums[j] - (double) fr[j] * mid;
for(int j = n; j > 0; --j)
sp[j] = nw[j] + sp[j + 1];
int rit = l + 1, sz = 0, rt = 0, ok = 0;
for(int j = 1; j <= n - l + 1; ++j){
while(sz && dq[rt - sz + 1] < j + l)
--sz;
while(rit <= n && rit <= j + u){
dq[++rt] = rit;
while(sz > 1 && sp[dq[rt]] < sp[dq[rt - 1]]){
dq[rt - 1] = dq[rt];
--sz;
--rt;
}
++rit;
}
if(sp[j] - sp[dq[rt - sz + 1]] >= 0)
ok = 1;
}
if(ok){
left = mid;
}
else
right = mid;
}
out << mid;
return 0;
}