Cod sursa(job #136137)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 15 februarie 2008 04:12:01
Problema Secventa 3 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<stdio.h>
long int n,l,u,i,lh,h[30002],ph[30002],start,cap,coada,ps,aux;
double c[30002],t[30002],sol,sc,cit;
void hu(long int ic);
double val(long int i0);
void hd(long int ic);
void sh(long int i1,long int i2);
int main()
{
	FILE *f,*g;f=fopen("secv3.in","r");g=fopen("secv3.out","w");
	fscanf(f,"%ld%ld%ld",&n,&l,&u);
	for(i=1;i<=n;i++){ fscanf(f,"%lf",&cit);c[i]=c[i-1]+cit;}
	for(i=1;i<=n;i++){ fscanf(f,"%lf",&cit);t[i]=t[i-1]+cit;}
	for(i=l;i<=u;i++){lh++;h[lh]=i;ph[i]=lh;hu(lh);}
	start=0;cap=l;coada=u;
	sol=val(1);
	while(coada<n)
	{ ps=ph[cap];h[ps]=h[lh];ph[h[ps]]=ps;lh--;
	  start++;cap++;coada++;
	  hd(ps);
	  lh++;h[lh]=coada;ph[coada]=lh;
	  hu(lh);
	  sc=val(1);
	  if(sol<sc)sol=sc;
	}
	while(cap<n)
	{ ps=ph[cap];h[ps]=h[lh];ph[h[ps]]=ps;lh--;
	  start++;cap++;
	  hd(ps);hu(ps);
	  sc=val(1);
	  if(sol<sc)sol=sc;
	}
	fprintf(g,"%.2lf",sol);
	fcloseall();
	return 0;
}
void hu(long int ic)
{
	long int is=ic/2;
	if(!is)return;
	if(val(is)<val(ic)){sh(is,ic);hu(is);}
}
double val(long int i0)
{  return (c[h[i0]]-c[start])/(t[h[i0]]-t[start]);}
void hd(long int ic)
{
	long int is,is1;
	is=2*ic;is1=2*ic+1;
	if(is>lh)return;
	if(is<lh)if(val(is1)>val(is))is=is1;
	if(val(is)>val(ic)){sh(is,ic);hd(is);}
}
void sh(long int i1,long int i2)
{
	aux=h[i1];h[i1]=h[i2];h[i2]=aux;
	ph[h[i1]]=i1;ph[h[i2]]=i2;
}