Cod sursa(job #935656)

Utilizator blasterzMircea Dima blasterz Data 4 aprilie 2013 13:17:25
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <cmath>
#define EPS 1e-4
#define N 30001
int a[N], b[N];
int deque[N];
int l, r;
double S[N];
int L, R, n;

void remove(int p) {
    while (l <= r && deque[l] == p - R)
        ++l;
}
void insert(int p) {
    while (l <= r && S[p - L] < S[ deque[r] ])
        --r;
    deque[++r] = p - 1;
}

bool isOk(double v) {
    int i;
    S[0] = 0;
    for (i = 1; i <= n; ++i)
        S[i] = S[i - 1] + a[i] - double(b[i]) * v;
    
    l = 1; r = 0;

    for (i = 1; i <= n; ++i) {
        remove(i);
        insert(i);
        if (S[i] - S[ deque[l] ] > 0)
            return true;
    }
    
    return false;
}

void solve() {
    double i, cnt;
    for (i = 0.0, cnt = (double)(1 << 30); cnt > EPS ; cnt /= 2.0)
        if (isOk(i + cnt))
            i += cnt;
    printf ("%.2lf\n", i);
}

int main() {
    freopen ("secv3.in", "r", stdin);
    freopen ("secv3.out", "w", stdout);
    scanf ("%d %d %d\n", &n, &L, &R);
    int i;
    for (i = 1; i <= n; ++i)
        scanf ("%d ", &a[i]);
    for (i = 1; i <= n; ++i)
        scanf ("%d ", &b[i]);
    solve();
}