Cod sursa(job #195553)

Utilizator AndreyPAndrei Poenaru AndreyP Data 19 iunie 2008 17:31:03
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,x,l;
int v[100010];
double r;
struct lup
{
	int a,b;
};
lup a[100010];
inline int father(int k)
{
	return k>>1;
}
inline int left_son(int k)
{
	return k<<1;
}
inline int right_son(int k)
{
	return (k<<1)+1;
}
/*void upheap(int k)
{
	if((k==1)||(v[k]<=v[father(k)]))
		return;
	swap(v[k],v[father(k)]);
	upheap(father(k));
}
void downheap(int h,int k)
{
	int max1=k;
	if(left_son(k)<=h)
	{
		if(v[left_son(k)]>v[max1])
			max1=left_son(k);
	}
	if(right_son(k)<=h)
	{
		if(v[right_son(k)]>v[max1])
			max1=right_son(k);
	}
	if(max1!=k)
	{
		swap(v[max1],v[k]);
		downheap(h,max1);
	}
}*/
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;
	/*if(o.a<p.a)
		return false;
	if(o.b>p.b)
		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);
		}
		r+=v[1];
		v[1]=v[c];
		c--;
		downheap(1,c);
	}
	printf("%.0lf\n",r);
	return 0;
}