Cod sursa(job #195564)

Utilizator AndreyPAndrei Poenaru AndreyP Data 19 iunie 2008 18:11:23
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define father(k) k>>1
#define left_son(k) k<<1
#define right_son(k) (k<<1)+1
int n,x,l;
int v[100010];
long long r;
struct lup
{
	int a,b;
};
lup a[100010];
void upheap(int k)
{
	int key=v[k];
	while((k>1)&&(key>v[father(k)]))
	{
		v[k]=v[father(k)];
		k=father(k);
	}
	v[k]=key;
}
void downheap(int k,int h)
{
	int son;
	do
	{
		son=0;
		if(left_son(k)<=h)
		{
			son=left_son(k);
			if(right_son(k)<=h)
			{
				if(v[left_son(k)]<v[right_son(k)])
					son=right_son(k);
			}
			if(v[k]>=v[son])
				son=0;
		}
		if(son)
		{
			swap(v[k],v[son]);
			k=son;
		}
	}while(son);
}
bool compar(const lup &o,const lup &p)
{
	if(o.a>p.a)
		return true;
	return false;
}
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d%d%d",&n,&x,&l);
	int i,c=0,j=0;
	for(i=0; i<n; i++)
	{
		scanf("%d%d",&a[i].a,&a[i].b);
		if(a[i].a<=x)
			a[i].a=(x-a[i].a)/l;
		else
		{
			i--;
			n--;
		}
	}
	sort(a,a+n,compar);
	for(i=a[0].a; i>=0; i--)
	{
		for(; (j<n)&&(a[j].a==i); j++)
		{
			v[++c]=a[j].b;
			upheap(c);
		}
		if(c)
		{
			r+=v[1];
			v[1]=v[c];
			c--;
			if(c)
				downheap(1,c);
		}
	}
	printf("%lld\n",r);
	return 0;
}