Cod sursa(job #1259156)

Utilizator SmarandaMaria Pandele Smaranda Data 9 noiembrie 2014 19:19:20
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <iomanip>
#include <fstream>

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 ++;
        }
    }
    return 0;
}

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

    freopen ("secv3.in", "r", stdin);
    ofstream fout ("secv3.out");

    scanf ("%d%d%d", &n, &l, &r);
    for (i = 1; i <= n; i ++) {
        scanf ("%d",&c [i]);
        c [i] = c [i] * 1000;
    }
    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 / 1000;
    fout << fixed << setprecision(2) << ans;
    return 0;
}