Cod sursa(job #1068408)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 28 decembrie 2013 12:29:14
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

const int Nmax = 30001;

int timp[Nmax];
int cost[Nmax];

double v[Nmax];
double sum[Nmax];

deque <int> deck;

int N, L, U;

int valid( double cst )
{
    double maxim = -10000000000.0f;

    for ( int i = 1; i <= N; ++i )
    {
        v[i] = 1.0 * cost[i] - 1.0 * timp[i] * cst;

        sum[i] = sum[i - 1] + v[i];
    }

    deck.clear();

    for ( int i = L; i <= N; ++i )
    {
        while ( deck.size() && sum[ deck.back() ] >= sum[i - L] ) deck.pop_back();
        while ( deck.size() && deck.front() < i - U ) deck.pop_front();

        deck.push_back( i - L );

        maxim = max( maxim, sum[i] - sum[ deck.front() ] );
    }

    return ( maxim >= 0.0 );
}

double cautare_binara()
{
    double sol = 0;
    double st = 0;
    double dr = 1000;
    double m;

    while ( dr - st > 0.01 )
    {
        m = ( st + dr ) / 2.0;

        if ( valid( m ) )
        {
            sol = m;
            st = m;
        }
        else
        {
            dr = m;
        }
    }

    return sol;
}

int main()
{
    ifstream f("secv3.in");
    ofstream g("secv3.out");

    f >> N >> L >> U;

    for ( int i = 1; i <= N; ++i )
    {
        f >> cost[i];
    }

    for ( int i = 1; i <= N; ++i )
    {
        f >> timp[i];
    }

    g << fixed << setprecision( 2 );
    g << cautare_binara();

    return 0;
}