Cod sursa(job #517791)

Utilizator crushackPopescu Silviu crushack Data 29 decembrie 2010 21:51:48
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>
#include <algorithm>
#define NMax 100000
using namespace std;

const char IN[]="lupu.in",OUT[]="lupu.out";

int N,X,L;
struct oaie{
	int x,d;
} a[NMax] , m[NMax];


bool cmp(oaie a,oaie b)
{
	return a.d<b.d;
}

bool cmp2(oaie a,oaie b)
{
	return a.x<b.x;
}

int main()
{
	int i,p,l,TMax=0;
	long long s=0;
	freopen(IN,"r",stdin);
	scanf("%d%d%d",&N,&X,&L);
	for (i=0;i<N;i++)
	{
		scanf("%d%d",&a[i].d,&a[i].x);
		a[i].d= (X-a[i].d)/L + 1;
		TMax= (a[i].d>TMax) ? a[i].d : TMax;
	}
	fclose(stdin);
	
	sort(a,a+N,cmp);

	for (l=0,i=N-1,p=TMax;i>0 && a[i].d>0 && p>0 ;p--)
	{
		for (; i>0 && a[i].d == p ;i--)
		{
			m[l++]=a[i];
			push_heap(m,m+l,cmp2);
		}
		if (l>0)
		{
			s+= m[0].x;
			pop_heap(m,m+l,cmp2);
			l--;
		}
	}
	
	freopen(OUT,"w",stdout);
	printf("%lld\n",s);
	fclose(stdout);
	
	return 0;
}