Cod sursa(job #1986592)

Utilizator giotoPopescu Ioan gioto Data 28 mai 2017 18:30:47
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
using namespace std;

int n, l, r, a[30005], b[30005], dq[30005];
long double s[30005];
inline bool check(long double v){
    int Front = 1, Back = 0;
    for(int i = 1; i < l ; ++i){
        long double val2 = a[i] - v * b[i];
        s[i] = s[i - 1] + val2;

    }
    for(int i = l; i <= n ; ++i){
        long double val = a[i - l] - v * b[i - l];
        long double val2 = a[i] - v * b[i];
        s[i] = s[i - 1] + val2;
        while(Back >= Front && s[i - l] <= s[dq[Back]]) --Back;
        dq[++Back] = i - l;
        while(dq[Front] <= i - r) ++Front;
        if(s[i] - s[dq[Front]] >= 0) return 1;
    }
    return 0;
}
int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    scanf("%d%d%d", &n, &l, &r);
    for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n ; ++i) scanf("%d", &b[i]);
    long double st = 0, dr = 30000000;
    while(dr - st >= 1e-8){
        double mij = (st + dr) / 2;
        if(check(mij)) st = mij;
        else dr = mij;

    }
    printf("%0.2lf", dr);
    return 0;
}