Cod sursa(job #934794)

Utilizator VmanDuta Vlad Vman Data 31 martie 2013 14:54:01
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>

const int N = 30003;
int n, l, u, a[N], b[N], dq[N];
int st, dr;
double s[N];
const double eps = 1e-2;

void scoate_u(int poz) {
    if (st <= dr && dq[st] == poz - u)
        ++ st;
}

void scoate_l(int poz) {
    while (dr >= st && s[poz - l] < s[dq[dr]])
        -- dr;
}

bool check(double val) {
    st = 1, dr = 0;
    
    for (int i = 1; i <= n; ++ i)
        s[i] = s[i - 1] + a[i] - val * (double)b[i];
    
    for (int i = l; i <= n; ++ i) {
        scoate_u(i);
        scoate_l(i);
        dq[++dr] = i - l;
        if (s[i] - s[dq[st]] > - eps)
            return 1;
    }
    
    return 0;
}

double cauta() {
    double mij, sol = 0, s = 0, d = 1 << 30;
    
    while (s + eps < d) {
        mij = (s + d) * 0.5;
        
        if (check(mij)) {
            sol = mij;
            s = mij;
        } else
            d = mij;
    }
    
    return sol;
}

int main() {
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    
    scanf("%d%d%d", &n, &l, &u);
    for (int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++ i)
        scanf("%d", &b[i]);
    
    printf("%.2lf", cauta());
    
    return 0;
}