Pagini recente » Istoria paginii runda/max_min/clasament | Cod sursa (job #1779626) | Cod sursa (job #2733848) | Cod sursa (job #658025) | Cod sursa (job #136130)
Cod sursa(job #136130)
#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;
}