Pagini recente » Monitorul de evaluare | Cod sursa (job #395998) | Cod sursa (job #419970) | Cod sursa (job #328156) | Cod sursa (job #1135685)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin ("secv3.in");
ofstream fout ("secv3.out");
const int N = 3e4 + 5;
const double eps = 1e-4;
deque <int> D;
int n, l, u;
double v[N], w[N], sp[N];
bool go(double x) {
double sum_max = -1e4;
for (int i = 1; i <= n; ++i)
sp[i] = sp[i-1] + v[i] - w[i] * x;
sum_max = sp[l];
for (int i = l + 1; i <= n; ++i) {
while (!D.empty() && sp[D.back()] >= sp[i - l])
D.pop_back();
D.push_back (i - l);
while (!D.empty() && D.front() < i - u)
D.pop_front();
sum_max = max(sum_max, sp[i] - sp[D.back()]);
}
if (sum_max > 0.0)
return 1;
return 0;
}
int main() {
fin >> n >> l >> u;
for (int i = 1; i <= n; ++i)
fin >> v[i];
for (int i = 1; i <= n; ++i)
fin >> w[i];
double sol = 0;
for (double step = 1e8; step > eps; step /= 2.0)
if (go (sol + step))
sol += step;
fout << sol;
}