Cod sursa(job #271425)

Utilizator diannaDiaconu Diana dianna Data 5 martie 2009 12:05:25
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<fstream.h>
ifstream f("lupu.in");
ofstream g("lupu.out");
#define nmax 101000
struct vect
{
	long inf,pct;
}h[nmax],h2[nmax];
long n,m,x,l,y,z,s,n2;
void urca(int k)
{
	if(k>1&&h[k].inf>h[k/2].inf)
	{
		vect z=h[k];
		h[k]=h[k/2];
		h[k/2]=z;
		urca(k/2);
	}
}
void coboara(int k,int n)
{
	long fiu=k;
	if(2*k<=n)
	{
		if(h[fiu].inf<h[2*k].inf)
			fiu=2*k;
		if(h[fiu].inf<h[2*k+1].inf&&2*k+1<=n)
			fiu=2*k+1;
		if(fiu!=k)
		{
			vect z=h[fiu];
			h[fiu]=h[k];
			h[k]=z;
			coboara(fiu,n);
		}
	}
}
void refacere(int n)
{
	if(n>0)
	{
	vect z=h[1];
	h[1]=h[n];
	h[n]=z;  n--;
	coboara(1,n);
	refacere(n);
	}
}
void citire()
{
 f>>m>>x>>l;     n=m;
 for(long i=1;i<=m;i++)
 {
	f>>y>>z;
	y=(x-y)/l;
	h[i].inf=y;
	h[i].pct=z;
	urca(i);
 }
}

void coboara2(int k,int n)
{
	long fiu=k;
	if(2*k<=n)
	{
		if(h2[fiu].pct<h2[2*k].pct)
			fiu=2*k;
		if(h2[fiu].pct<h2[2*k+1].pct&&2*k+1<=n)
			fiu=2*k+1;
		if(fiu!=k)
		{
			vect z=h2[fiu];
			h2[fiu]=h2[k];
			h2[k]=z;
			coboara(fiu,n);
		}
	}
}
void urca2(int k)
{
	if(k>1&&h2[k].pct>h2[k/2].pct)
	{
		vect z=h2[k];
		h[k]=h2[k/2];
		h2[k/2]=z;
		urca(k/2);
	}
}
void program()

{
	long v=h[m].inf;
	long i=m;
	while(v>=0&&i>0)
	{
		v=h[i].inf;
		while(v==h[i].inf&&i>0)
		{
			h2[++n2]=h[i];
			urca2(n2);
			i--;
		}
		long j=v-h[i].inf;
		while(j>0&&n2>0)
		{
			s+=h2[1].pct;
			h2[1]=h2[n2];
			n2--;
			coboara2(1,n2);
			j--;
		}
	}
}
void afisare()
{
	g<<s<<'\n';
}
int main()
{
	citire();
	refacere(n);
	program();
	afisare();
f.close();
g.close();
return 0;


}