Cod sursa(job #1099797)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 6 februarie 2014 12:27:50
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>

using namespace std;

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

const int Nmax = 30100;
const int oo = 0x3f3f3f3f;

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

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

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

    sol = imp(C[L], T[L]);
    for(int i = L + 1; i <= N; i++)
    {
        int t = T[i - L], c = C[i - L];
        int st, dr, cost ,timp;

        while(!DT.empty() && T[DT.back()] >= t)
            DT.pop_back();
        DT.push_back(i - L);
        while(!DC.empty() && T[DC.back()] <= c)
            DC.pop_back();
        DC.push_back(i - L);

        if(DT.front() <= i - U)
            DT.pop_front();
        if(DC.front() <= i - U)
            DC.pop_front();

        st = DT.front(), dr = i;
        cost = C[i] - C[st], timp = T[i] - T[st];
        sol = max(sol, imp(cost, timp));

        st = DC.front(), dr = i;
        cost = C[i] - C[st], timp = T[i] - T[st];
        sol = max(sol, imp(cost, timp));
    }

    fout.precision(4);
    fout << fixed << sol;
    return 0;
}