Cod sursa(job #2316426)

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

using namespace std;

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

int main()
{
	freopen("secv3.in","r",stdin);
	freopen("secv3.out","w",stdout);
    scanf("%d%d%d",&n,&l,&u);
    for(i=1;i<=n;i++)scanf("%lf",&c[i]);
    for(i=1;i<=n;i++){scanf("%lf",&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;
        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;
    }
	printf("%.2lf",ans);
    return 0;
}