Cod sursa(job #2212183)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 13 iunie 2018 15:59:08
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <iomanip>
using namespace std;

ifstream cin("secv3.in");
ofstream cout("secv3.out");

const double LIM = 1e-3;

int v[30007], a[30007], dq[30007];

double s[30007];

int n, l, u;

bool cool(double lol) {
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + v[i] - a[i] * lol;
    }
    int st(0), dr(-1);
    for (int i = 1; i <= n; ++i) {
        while (i > u && st <= dr && dq[st] < i - u) {
            ++st;
        }
        if (i >= l) {
            while (st <= dr && s[dq[dr]] >= s[i - l]) {
                --dr;
            }
            dq[++dr] = i - l;
            if (s[i] - s[dq[st]] >= 0) {
                return true;
            }
        }
    }
    return false;
}

double cb() {
    double pas = 1<<9, r(0);
    while (pas > LIM) {
        if (cool(r + pas)) {
            r += pas;
        }
        pas /= 2.0;
    }
    return r;
}

int main()
{
    cin >> n >> l >> u;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    cout << setprecision(2) << fixed;
    cout << cb();
    return 0;
}