Cod sursa(job #999491)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 20 septembrie 2013 15:52:32
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <deque>
#define NMax 30010

using namespace std;

int n, l, u;
int cost[NMax], timp[NMax];
double sol;

inline void Read()
{
    ifstream f ("secv3.in");
    f>>n>>l>>u;
    int i;
    for (i=1; i<=n; ++i)
        f>>cost[i];
    for (i=1; i<=n; ++i)
        f>>timp[i];
    f.close();
}

inline bool Verif (double x)
{
    double aux[NMax], sum[NMax], solaux = -1000000000.0;
    int st, dr;
    deque <int> dq;
    sum[0] = 0.0;
    for (int i=1; i<=n; ++i)
        aux[i] = 1.0*cost[i] - x*timp[i],
        sum[i] = sum[i-1] + aux[i];
    st = 0, dr = l;
    dq.push_back(st);
    for (; dr<=n; ++dr)
    {
        while (!dq.empty() && dr-dq.front() > u)
            dq.pop_front();

        while (!dq.empty() && sum[dr-l] <= dq.back())
            dq.pop_back();

        dq.push_back(dr-l);
        solaux = max(solaux, sum[dr] - sum[dq.front()]);
    }
    if (solaux >= 0.0)
        return true;
    return false;
}


inline void Solve()
{
    double st, dr, mij;
    st = 0.0, dr = 1000.0;
    while (dr-st > 0.001)
    {
        mij = (st+dr)/2.0;
        if (Verif(mij))
        {
            sol = mij;
            st = mij + 0.001;
        }
        else
            dr = mij - 0.001;
    }
}

inline void Write()
{
    freopen ("secv3.out", "w", stdout);
    printf("%.2lf\n", sol);
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}