Cod sursa(job #136130)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 15 februarie 2008 03:48:21
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<stdio.h>
long int n,l,u,i,lh,h[30002],ph[30002],start,ps,cap,coada,aux,ii1,ii2;
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;
	ii1=0;ii2=h[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);
	  if((c[h[1]]-c[start])*(t[ii2]-t[ii1])>(c[ii2]-c[ii1])*(t[h[1]]-t[start]))
	  { ii1=start;ii2=h[1];}
	}
	while(cap<n)
	{ ps=ph[cap];h[ps]=h[lh];ph[h[ps]]=ps;lh--;
	  start++;cap++;
	  hd(ps);
	  if((c[h[1]]-c[start])*(t[ii2]-t[ii1])>(c[ii2]-c[ii1])*(t[h[1]]-t[start]))
	  { ii1=start;ii2=h[1];}
	}
	sol=(t[ii2]-t[ii1])/(c[ii2]-c[ii1]);
	fprintf(g,"%.2lf",sol);
	fcloseall();
	return 0;
}
void hu(long int ic)
{
	long int is=ic/2;
	if(!is)return;
	if((c[h[is]]-c[start])*(t[h[ic]]-t[start])<(c[h[ic]]-c[start])*(t[h[is]]-t[start])){sh(is,ic);hu(is);}
}
void hd(long int ic)
{
	long int is,is1;
	is=2*ic;is1=2*ic+1;
	if(is>lh)return;
	if(is<lh)
	if((c[h[is1]]-c[start])*(t[h[is]]-t[start])>(c[h[is]]-c[start])*(t[h[is1]]-t[start]))is=is1;
	if((c[h[is]]-c[start])*(t[h[ic]]-t[start])>(c[h[ic]]-c[start])*(t[h[is]]-t[start])){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;
}