Pagini recente » Cod sursa (job #2386783) | Cod sursa (job #2835868) | Cod sursa (job #543300) | Istoria paginii runda/testare | Cod sursa (job #1135693)
#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) {
D.clear();
for (int i = 1; i <= n; ++i)
sp[i] = sp[i-1] + v[i] - w[i] * x;
double sum_max = sp[l];
D.push_back (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 = 4e7; step > eps; step /= 2.0)
if (go (sol + step))
sol += step;
fout << sol;
}