Cod sursa(job #346793)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 9 septembrie 2009 18:22:20
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100001
struct lupu{int l,d;}v[N];
int n,nr,x,l,h[N];
bool compar(const lupu&a,const lupu&b)
{
	if (a.d>b.d)
		return true;
	if (a.d==b.d&&a.l>b.l)
		return true;
	return false;
}
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)
	{
		scanf("%d%d",&v[i].d, &v[i].l);
		v[i].d=(x-v[i].d)/l;
	}
	sort (v+1,v+1+n,compar);
}
void urc(int k)
{
	int key=h[k];
	while (k-1&&key>h[k/2])
	{
		h[k]=h[k/2];
		k/=2;
	}
	h[k]=key;
}
void add(int k)
{
	h[++nr]=v[k].l;
	urc(nr);
}
void cobor(int k)
{
	int f=k;
	while (true)
	{
		if (2*k<=nr&&h[f]<h[2*k])
			f=2*k;
		if (2*k+1<=nr&&h[f]<h[2*k+1])
			f=2*k+1;
		if (f==k)
			return ;
		int aux=h[k];
		h[k]=h[f];
		h[f]=aux;
		k=f;
	}
}
void del(int k)
{
	h[k]=h[nr];
	--nr;
	if (k-1&&h[k]>h[k/2])
		urc(k);
	else
		cobor(k);
}
void build()
{
	int j=1;long long lana=0;
	for (int i=v[1].d;i>=0; --i)
	{
		while (j<=n&&v[j].d==i)
		{
			add(j);
			++j;
		}
		if (nr)
		{
			lana+=h[1];
			del(1);
		}
	}
	printf("%lld",lana);
}
int main()
{
	citire();
	build();
	return 0;
}