Pagini recente » Cod sursa (job #3236470) | Cod sursa (job #3254346) | Cod sursa (job #3213523) | Cod sursa (job #363754) | Cod sursa (job #3229594)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 30000;
int N, L, U;
int C[MAX + 3], T[MAX + 3];
double V[MAX + 3];
double bs(double X) {
deque<int>dq;
for(int i = 1; i <= N; i++) {
V[i] = C[i] - X * T[i];
}
for(int i = 1; i <= N; i++) {
cout << V[i] << ' ';
}
cout << '\n';
double ans = -INT_MAX;
int ri = 0;
for(int i = 1; i <= N; i++) {
while(ri < i - L) {
ri++;
while(!dq.empty() && V[dq.front()] > V[ri]) dq.pop_front();
dq.push_front(ri);
}
while(!dq.empty() && dq.back() < i - U) dq.pop_back();
if(!dq.empty())
ans = max(ans, V[i] - V[dq.back()]);
}
//cout << ans << '\n';
return ans;
}
int main() {
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
cin >> N >> L >> U;
for(int i = 1; i <= N; i++) {
cin >> C[i];
C[i] += C[i - 1];
}
for(int i = 1; i <= N; i++) {
cin >> T[i];
T[i] += T[i - 1];
}
double st = 0, dr = MAX;
double best = 0;
while(dr - st >= 0.001) {
//cout << st << ' ' << dr << '\n';
double mid = (st + dr) / 2;
if(bs(mid) >= 0) st = mid, best = max(best, mid);
else dr = mid;
}
cout << fixed << setprecision(2) << best;
}
/*
C / T = X (X maxim)
C[l] + C[l + 1] ... + C[r] = X * T[l] + X * T[l + 1] + ... X * T[r]
C[l] + C[l + 1] + ... + C[r] - X * T[l] - X * T[l + 1] - ... - X * T[r] >= 0
*/