Cod sursa(job #340025)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 12 august 2009 18:17:44
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<cstdio>
#define N 100001
#include<algorithm>
using namespace std;
int n,nh,l,x;
long long s,g;
struct lupu{int l,d;}h[N],aux,key;
bool compar(const lupu&a, const lupu&b)
{
	return a.l>b.l;
}
void cobor(int k)
{
	int fiu;
	do
	{
		fiu=0;
		if (2*k<=nh)
		{
			fiu=2*k;
			if (2*k+1<=nh)
				if ((h[fiu].l<h[2*k+1].l)||((h[fiu].l==h[2*k+1].l)&&(h[fiu].d<h[2*k+1].d)))	
					fiu=2*k+1;
			if (h[fiu].l<h[k].l)
				fiu=0;
		}
		if (fiu)
		{
			aux=h[k];
			h[k]=h[fiu];
			h[fiu]=aux;
			k=fiu;
		}
	}
	while(fiu);
}
void urc(int k)
{
	key=h[k];
	while (k-1&&((key.l>h[k/2].l)||((key.l==h[k/2].l)&&(key.d>h[k/2].d))))
	{
		h[k]=h[k/2];
		k/=2;
	}
	h[k]=key;
}
void cut(int k)
{
	h[k]=h[nh];
	--nh;
	if (k-1&&((key.l>h[k/2].l)||((key.l==h[k/2].l)&&(key.d>h[k/2].d))))
		urc(k);
	else
		cobor(k);
}
void solve()
{
	while (nh)
	{
		s+=h[1].l;
		cut (1);
		g+=l;
		while (h[1].d+g>x&&nh)
			cut(1);
	}
}
void citire()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d%d%d",&n,&x,&l);
	for (int i=1; i<=n; ++i)
	{
		int x2,y;
		scanf("%d%d",&x2,&y);
		if (x2<=x)
		{
			h[++nh].d=x2;
			h[nh].l=y;
		}
			
	}
	sort (h+1,h+nh+1,compar);
	for (int i=nh/2; i; --i)
		cobor(i);
}
void afis()
{
	/*for (int i=1; i<=n; ++i)
		printf("%d %d\n",h[i].d,h[i].l);*/
	printf("%lld",s);
}
int main()
{
	citire();
	solve();
	afis();
	return 0;
}