Pagini recente » Cod sursa (job #2475171) | Cod sursa (job #3001715) | Cod sursa (job #1543626) | Cod sursa (job #2441538) | Cod sursa (job #3185013)
/*
cb x (ans):
(c[i] - c[j]) / (t[i] - t[j]) >= x
<=> (c[i] - t[i] * x) - (c[j] - t[j] * x) >= 0
<=> max(d[i] - d[j]) >= 0 cu i - u <= j <= i - l
*/
#include <fstream>
#include <iomanip>
#include <vector>
#include <deque>
using namespace std;
ifstream cin("secv3.in");
ofstream cout("secv3.out");
double get_max_lin(double x, vector<double>& c, vector<double>& t, int l, int u) {
int n = c.size() - 1;
vector<double> d(n + 1);
for (int i = 1; i <= n; i++) {
d[i] = c[i] - x * t[i];
}
double ans = d[l];
deque<pair<double, int>> stk;
for (int i = l; i <= n; i++) {
while (!stk.empty() && stk.back().first > d[i - l]) {
stk.pop_back();
}
stk.push_back({d[i - l], i - l});
ans = max(ans, d[i] - stk.front().first);
if (stk.front().second == i - u) {
stk.pop_front();
}
}
return ans;
}
double cb(vector<double>& c, vector<double>& t, int l, int u) {
double st = 0;
double dr = 3e7;
for (int i = 0; i < 100; i++) {
double mid = (st + dr) / 2;
if (get_max_lin(mid, c, t, l, u) >= 0) {
st = mid;
} else {
dr = mid;
}
}
return (st + dr) / 2;
}
void Solve() {
int n; cin >> n;
int l, u; cin >> l >> u;
vector<double> c(n + 1);
for (int i = 1; i <= n; i++) {
cin >> c[i];
c[i] += c[i - 1];
}
vector<double> t(n + 1);
for (int i = 1; i <= n; i++) {
cin >> t[i];
t[i] += t[i - 1];
}
cout << fixed << setprecision(3) << cb(c, t, l, u) << "\n";
}
int main() {
Solve();
return 0;
}