Cod sursa(job #644419)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 6 decembrie 2011 16:05:05
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <deque>

#define NMax 30005
#define Infinity 20

using namespace std;

int N, L, U, C[NMax], T[NMax];
double X[NMax], Solution;
deque <int> D;

void Read ()
{
    freopen ("secv3.in", "r", stdin);
    scanf ("%d %d %d", &N, &L, &U);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d", &C[i]);
    }
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d", &T[i]);
    }
}

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

bool Solve (double S)
{
    for (int i=1; i<=N; ++i)
    {
        X[i]=X[i-1]+C[i]-T[i]*S;
    }
    for (int i=L; i<=N; ++i)
    {
        while (!D.empty () and X[D.back ()]>=X[i-L+1])
        {
            D.pop_back ();
        }
        D.push_back (i-L);
        while (D.front ()<i-U)
        {
            D.pop_front ();
        }
        if (X[i]-X[D.front ()]>=0)
        {
            D.clear ();
            return true;
        }
    }
    D.clear ();
    return false;
}

int main()
{
    Read ();
    double Left=0, Right=Infinity;
    while (Right-Left>0.0001)
    {
        double Mid=(Left+Right)/2;
        if (Solve (Mid))
        {
            Left=Mid+0.0001;
            Solution=Mid;
        }
        else
        {
            Right=Mid-0.0001;
        }
    }
    Print ();
    return 0;
}