Cod sursa(job #1099895)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 6 februarie 2014 13:34:13
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <memory.h>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

const int Nmax = 30100;
const int oo = 0x3f3f3f3f;
const double EPS = 0.001;

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

double imp(double A, double B) {return A / B;}

bool OK(double V)
{
    double AUX[Nmax], S[Nmax], sol;
    memset(AUX, 0.0, sizeof AUX);
    memset(S, 0.0, sizeof S);
    D.clear();

    for(int i = 1; i <= N; i++)
    {
        AUX[i] = 1.0 * C[i] - T[i] * V;
        S[i] = S[i - 1] + AUX[i];
    }

    sol = S[L];
    for(int i = L + 1; i <= N; i++)
    {
        int V = i - L;
        while(!D.empty() && S[D.back()] >= V) D.pop_back();
        D.push_back(i - L);

        if(D.front() <= i - U)
            D.pop_front();
        sol = max(sol, S[i] - S[D.front()]);
    }

    if(sol > 0.0)
        return 1;
    return 0;
}

int main()
{
    fin >> N >> L >> U;
    for(int i = 1; i <= N; i++)
        fin >> C[i];
    for(int i = 1; i <= N; i++)
        fin >> T[i];

    double st = 0, dr = 30e6 + 100, mid;
    while(dr - st > EPS)
    {
        mid = (st + dr) / 2.0;
        if(OK(mid))
            st = mid;
        else
            dr = mid;
    }

    fout.precision(2);
    fout << fixed << st;
    return 0;
}