Cod sursa(job #1998053)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 6 iulie 2017 14:05:40
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

int x[30001], y[30001], Deque[30001];
int l, r, n, i, Front, Back, k;
double s[30001];
double st, dr, m;

bool verif(double mid)
{
    for(i=1; i<=n; ++i)
    {
        s[i]=s[i-1]+x[i]-y[i]*mid;
    }

    Front=1; Back=0;

    for(i=1; i<=n; ++i)
    {
        while(Front<=Back && s[i]<=s[Deque[Back]]) --Back;
        Deque[++Back]=i;
        if(i-Deque[Front]==k) ++Front;
        if(i+l<=n)
        {
            if(s[i+l]-s[Deque[Front]]>0) return 1;
        }
    }
    return 0;
}

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

    fin>>n>>l>>r;
    k=r-l+1;
    for(i=1; i<=n; ++i) fin>>x[i];
    for(i=1; i<=n; ++i) fin>>y[i];

    st=0; dr=30000000;
    while(dr-st>=0.001)
    {
        m=(st+dr)/2;
        if(verif(m)) st=m;
        else dr=m;
    }

    fout<<fixed<<setprecision(2)<<st<<"\n";
    return 0;
}