Cod sursa(job #2316424)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 11 ianuarie 2019 18:09:16
Problema Secventa 3 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,l,u,i,gi,gn,g,G[30010];
long double ans,c[30010],t[30010],d[30010];

int main()
{
    f>>n>>l>>u;
    for(i=1;i<=n;i++)f>>c[i];
    for(i=1;i<=n;i++){f>>t[i];d[i]=c[i]/t[i];c[i]+=c[i-1],t[i]+=t[i-1];}
    for(i=l;i<=n;i++)
        ans=max(ans,(c[i]-c[i-l])/(t[i]-t[i-l]));
    for(i=l+1;i<=n;i++)
        G[++g]=i;
	if(u>=2*l)u=2*l-1;
    for(i=l+1;i<=u&&g;i++)
    {
        if(G[1]==i-1)
            gi=2;
        else
            gi=1;
        gn=0;
        long double newans=0;
        for(;gi<=g;gi++)
        {
            if(d[G[gi]]<ans)continue;
            newans=max(newans,(c[G[gi]]-c[G[gi]-i])/(t[G[gi]]-t[G[gi]-i]));
            G[++gn]=G[gi];
        }
		if(newans<ans&&n>20000)break;
		ans=max(ans,newans);
        g=gn;
    }
    go<<ans;
    return 0;
}