Cod sursa(job #999502)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 20 septembrie 2013 16:11:05
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <deque>

#define In "secv3.in"
#define Out "secv3.out"
#define Nmax 30005
#define EPS 1e-2
#define Inf 0x3f3f3f3f
using namespace std;
int a[Nmax], b[Nmax];
int n,l,u;
double sum[Nmax],sol;
inline void Read()
{
    ifstream f(In);
    f>>n>>l>>u;
    int i;
    for(i = 1;i <=n; ++i)
        f>>a[i];
    for(i = 1 ;i<=n;++i)
        f>>b[i];
    f.close();
}

inline bool Verif(const double x)
{
    deque< int >D;
    int i;
    double Best = -1.0*Inf;
    for(i = 1;i <= n; ++i)
        sum[i]  = sum[i-1] + a[i]-b[i]*x;
    D.push_back(0);
    for(i = l;i <= n; ++i)
    {
        while(!D.empty() && sum[D.back()]>=sum[i-l])
            D.pop_back();
        D.push_back(i-l);
        while(D.front() < i-u)
            D.pop_front();
        Best = max(Best,sum[i]-sum[D.front()]);
    }
    return (Best>=0);
}

inline void Solve()
{
    double middle,Left=0,Right=1000;
    while(Right-Left>EPS)
    {
        middle =(Left+Right)/2.0;
        if(Verif(middle))
        {
            sol = middle;
            Left = middle;
        }
        else
            Right = middle;
    }
}

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

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