Cod sursa(job #1256778)

Utilizator SmarandaMaria Pandele Smaranda Data 6 noiembrie 2014 20:47:58
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>

using namespace std;

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

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

    while (i <= n) {
        h = sp [i] - sp [minD [p]];
        if (h > 0)
            return 1;
        while (p <= u && sp [minD [p]] > sp [i])
            p ++;
        minD [++ p] = i;
        while (p <= u && i - minD [p] > r)
            p ++;
        ++ i;
    }
    return 0;
}

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 = 200;
    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;
}