Cod sursa(job #1256813)

Utilizator SmarandaMaria Pandele Smaranda Data 6 noiembrie 2014 21:41:23
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>

using namespace std;

int n, l, r;
int c [30002], t [30002];
long long x [30002], sp [30002];

bool verif (int value) {
    int i, minD [30002], p, u, st, dr;
    long long h;
    //value = 100000000; // !!
    for (i = 1; i <= n; i ++) {
        x [i] = (long long)c [i] - t [i] * value;
        sp [i] = (long long)sp [i - 1] + x [i];
    }
    u = p = 1;
    minD [1] = 0;
    st = 0;
    dr = 0;
    for (i = l; i <= n; i ++) {
        h = sp [i] - sp [minD [p]];
        if (h >= 0)
            return 1;
        ++ dr;
        while (p <= u && sp [dr] < sp [minD [p]])
            p ++;
        minD [++ u] = dr;
        if (i + 1 - st > r) {
            st ++;
            while (p <= u && i - minD [p] > r)
                p ++;
        }
    }
}

int main () {
    int i, st, dr, m, last;
    double ans;

    freopen ("secv3.in", "r", stdin);
    freopen ("secv3.out", "w", stdout);

    scanf ("%d%d%d", &n, &l, &r);
    for (i = 1; i <= n; i ++) {
        scanf ("%d",&c [i]);
        c [i] = c [i] * 100;
    }
    for (i = 1; i <= n; i ++)
        scanf ("%d", &t [i]);
    st = 1;
    dr = 40000000;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (verif (m)) {
            last = m;
            st = m + 1;
        }
        else dr = m - 1;
    }
    ans = (double)last / 100;
    printf ("%.2lf", ans);
    return 0;
}