Cod sursa(job #195543)

Utilizator AndreyPAndrei Poenaru AndreyP Data 19 iunie 2008 17:06:17
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,x,l;
int v[100010],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);
	}
}
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--];
		downheap(c,1);
	}
	printf("%d\n",r);
	return 0;
}