Cod sursa(job #357145)

Utilizator proflaurianPanaete Adrian proflaurian Data 18 octombrie 2009 10:17:31
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<stdio.h>
int N,L,U,X,i,j,G[30002],P,aux,g,gi,gn;
double c[30002],t[30002],d[30002],sol,sc,dc;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	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];}
}
void solve()
{
	if(U>=2*L)U=2*L-1;
    for(P=L;P<=N;P++)
	{
		sc=(c[P]-c[P-L])/(t[P]-t[P-L]);
		sol=(sc>sol)?sc:sol;
	}
	for(P=L+1;P<=N;P++)
		G[++g]=P;
	for(X=L+1;X<=U;X++)
	{
		gi=1;if(G[1]==X-1)gi=2;
		gn=0;sc=0;
		for(;gi<=g;gi++)
		{
			P=G[gi];
			if(d[P]<sol)continue;
			dc=(c[P]-c[P-X])/(t[P]-t[P-X]);
			sc=sc>dc?sc:dc;
			G[++gn]=P;
		}
		g=gn;
		sol=sol>sc?sol:sc;
	}
	printf("%.2lf",sol);
}

/*void up(int F)
{
    int T=F>>1;
    if(!T)return;
    if(val(T)<val(F)){swap(F,T);up(T);}
}
double val(int I)
{  return (c[h[I]]-c[S])/(t[h[I]]-t[S]);}
void down(int T)
{
    int F=T<<1;
    if(F>H)return;
    if(F<H)if(val(F+1)>val(F))F++;
    if(val(F)>val(T)){swap(F,T);down(F);}
}
void swap(int I,int J)
{
    aux=h[I];h[I]=h[J];h[J]=aux;
    ph[h[I]]=I;ph[h[J]]=J;
}

*/