Cod sursa(job #2278136)

Utilizator CosaMateiMatei Cosa Gabriel CosaMatei Data 7 noiembrie 2018 12:37:18
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX=30001;

pair <float,float> v[NMAX];

int dq[NMAX];

int n,l,u,st,dr,x;

float ans=0.00;

int main()
{
    in>>n>>l>>u;
    for(int i=1;i<=n;++i)
    {
        in>>x;
        v[i].first=v[i-1].first+x;
    }
    for(int i=1;i<=n;++i)
    {
        in>>x;
        v[i].second=v[i-1].second+x;
    }
    st=1;
    dr=0;
    for(int i=1;i<=n-l+1;++i)
    {
        if(st<=dr && dq[st]==i-u)
            ++st;
        while(st<=dr && (v[dq[dr]].first-v[dq[st]-1].first+v[i].first-v[i-1].first) / (v[dq[dr]].second-v[dq[st]-1].second+v[i].second-v[i-1].second) < (v[i].first-v[i-1].first) / (v[i].second-v[i-1].second))
            --dr;
        dq[++dr]=i;
        if(i>=l)
            ans=max(ans,(float)((v[dq[dr]].first-v[dq[st]-1].first)/(v[dq[dr]].second-v[dq[st]-1].second)));
    }
    out<<setprecision(2)<<fixed<<ans;
    return 0;
}