Cod sursa(job #2151994)

Utilizator andrei32576Andrei Florea andrei32576 Data 5 martie 2018 09:37:52
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
#include<deque>
#include<iomanip>
using namespace std;

int n,l,u,i;
int c[30002],t[30002];
deque <int> dq;
double s;

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

double raport(int i,int j)
{
    return (1.0*(c[i]-c[j]))/(1.0*(t[i]-t[j]));
}

int main()
{
    f>>n>>l>>u;

    for(i=1;i<=n;i++)
    {
        f>>c[i];
        c[i]+=c[i-1];
    }
    for(i=1;i<=n;i++)
    {
        f>>t[i];
        t[i]+=t[i-1];
    }

    for(i=l;i<=n;i++)
    {
        if(!dq.empty() && dq.front()==i-u-1)
            dq.pop_front();

        while(!dq.empty() && raport(i,dq.back())<=raport(i,i-1))
            dq.pop_back();

        dq.push_back(i-1);

        s=max(s,raport(i,dq.front()));

    }

    g<<fixed<<setprecision(3)<<s;

    f.close();
    g.close();
    return 0;
}