Cod sursa(job #1135681)

Utilizator tudorv96Tudor Varan tudorv96 Data 8 martie 2014 11:23:03
Problema Secventa 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <deque>
using namespace std;

ifstream fin ("secv3.in");
ofstream fout ("secv3.out");

const int N = 3e4 + 5;
const double eps = 1e-2;

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 = 1e9; step > eps; step /= 2.0)
        if (go (sol + step))
            sol += step;
    fout << sol;
}