Pagini recente » Cod sursa (job #2112471) | Cod sursa (job #862717) | Cod sursa (job #186103) | Cod sursa (job #3131990) | Cod sursa (job #2891208)
#include <bits/stdc++.h>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
int n, l, u, a[30005], b[30005];
double s[30005];
double check(double val)
{
s[0] = 0;
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + a[i] - val * b[i];
deque<pair<double, int>>q;
double Max = -INT_MAX;
for (int i = l; i <= n; i++) {
while (!q.empty() && s[i - l] < q.back().first)
q.pop_back();
q.push_back({s[i - l], i - l});
if (!q.empty() && q.front().second < i - u)
q.pop_front();
Max = max(Max, s[i] - q.front().first);
}
return (Max >= 0);
}
double caut_bin()
{
double i = 0., step = (1 << 20) * 1.;
int cnt = 1;
while (cnt <= 30) {
//cout << check(i + step) << '\n';
if (check(i + step))
i += step;
step /= 2;
cnt++;
}
return i;
}
int main() {
in >> n >> l >> u;
for (int i = 1; i <= n; i++)
in >> a[i];
for (int i = 1; i <= n; i++)
in >> b[i];
double sol = caut_bin();
out << fixed << setprecision(2) << sol;
return 0;
}