Cod sursa(job #935752)

Utilizator blasterzMircea Dima blasterz Data 4 aprilie 2013 17:51:40
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 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] < S[ deque[r] ])
        --r;
    deque[++r] = p;
}

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 = L; i <= n; ++i) {
        remove(i);
        insert(i - L);
        if (S[i] - S[ deque[l] ] > 0)
            return true;
    }
    
    return false;
}

void solve() {
    double i, cnt;
    for (i = 0.0, cnt = (double)(1 << 28); cnt > EPS ; cnt /= 2.0)
        if (i + cnt <= (1 << 28) && 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();
}