Cod sursa(job #1756655)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 13 septembrie 2016 12:44:48
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
typedef double f64;

const int NMAX = 30005;
const f64  EPS = 1.e-3;

int n, a, b;
int c[NMAX],
    t[NMAX];
f64 s[NMAX];

bool check(f64 x) {
    deque<int> dq;

    for(int i=1; i<=n; ++i)
        s[i] = s[i-1]+c[i]-t[i]*x;

    dq.push_back(0);
    for(int i=a; i<=n; ++i) {
        while(!dq.empty() && i-dq.front()>b)
            dq.pop_front();

        if(s[i] - s[dq.front()] >= 0)
            return true;

        while(!dq.empty() && s[i-a+1]<=s[dq.back()])
            dq.pop_back();

        dq.push_back(i-a+1);
    }

    return false;
}

int main(void) {
    freopen("secv3.in",  "r", stdin);
    freopen("secv3.out", "w", stdout);
    f64 ant;

    scanf("%d%d%d", &n, &a, &b);
    for(int i=1; i<=n; ++i)
        scanf("%d", &c[i]);
    for(int i=1; i<=n; ++i)
        scanf("%d", &t[i]);

    ant = 0.;
    for(f64 m=1000.; m>EPS; m/=2.)
        if(check(ant+m))
            ant+= m;

    printf("%.2f\n", ant);

    fclose(stdin);
    fclose(stdout);
    return 0;
}