Cod sursa(job #356857)

Utilizator proflaurianPanaete Adrian proflaurian Data 17 octombrie 2009 08:24:38
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
long int N,L,U,i,H,h[30002],ph[30002],S,B,T,P,aux;
double c[30002],t[30002],sol,sc,cit,val(int I);
void read(),solve(),down(int F),up(int F),swap(int I,int J);
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",&cit);c[i]=c[i-1]+cit;}
    for(i=1;i<=N;i++){ scanf("%lf",&cit);t[i]=t[i-1]+cit;}
}
void solve()
{
    if(N<20000)
    {  U=(2*L<U)?2*L:U;
       for(P=L;P<=U;P++)
       { for(i=0;i<=N-P;i++)
         { sc=(c[i+P]-c[i])/(t[i+P]-t[i]);
           sol=(sc>sol)?sc:sol;
         }
       }
       printf("%.2lf",sol);
       return;
    }
    for(i=L;i<=U;i++){H++;h[H]=i;ph[i]=H;up(H);}
    S=0;B=L;T=U;
    sol=val(1);
    while(T<N)
    { P=ph[B];h[P]=h[H];ph[h[P]]=P;H--;
      S++;B++;T++;
      down(P);
      H++;h[H]=T;ph[T]=H;
      up(H);
      sc=val(1);
      if(sol<sc)sol=sc;
    }
    while(B<N)
    { P=ph[B];h[P]=h[H];ph[h[P]]=P;H--;
      S++;B++;
      down(P);up(P);
      sc=val(1);
      if(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;
}