Cod sursa(job #994534)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 5 septembrie 2013 18:19:07
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <deque>

#include <cstdio>
using namespace std;

const int MAX_N = 30002;
const double EPS = 0.01;

int N, L, U;
double C[MAX_N], T[MAX_N], S[MAX_N];
deque < pair < double, double > > D;
double sol;

inline int double_cmp(double a, double b) {
    if(a - b < -EPS)
        return -1;
    if(a - b > EPS)
        return 1;
    return 0;
}

inline bool check(double R) {
    while(!D.empty())
        D.pop_front();
    for(int i = 1; i < L; ++i)
        S[i] = S[i-1] + C[i] - R*T[i];
    for(int i = L, j = 0; i <= N; ++i, ++j) {
        while(!D.empty() && S[j] <= D.back().first)
            D.pop_back();
        D.push_back(make_pair(S[j], j));
        while(!D.empty() && D.front().second <= i-U)
            D.pop_front();
        S[i] = S[i-1] + C[i] - R*T[i];
        double Best = S[i] - D.front().first;
        if(double_cmp(Best, 0.0) >= 0)
            return 1;
    }
    return 0;
}

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("%lf", &C[i]);
    for(int i = 1; i <= N; ++i)
        scanf("%lf", &T[i]);

    double l = 0, m = 0, r = 1000000.0;
    while(double_cmp(l, r) <= 0) {
        m = (l+r)/2.0;
        if(check(m))
            sol = m, l = m+EPS;
        else r = m-EPS;
    }

    printf("%.2lf\n", sol);

    return 0;
}