Cod sursa(job #302319)

Utilizator znakeuJurba Andrei znakeu Data 8 aprilie 2009 20:02:55
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
using namespace std;

#include <stdio.h>
#include <queue>

const int MAXN = 100005;

struct oaie
{	long long lana,timp;	};

oaie A[MAXN];

int N; long long tMax=0,REZ=0;


int CMP(const void *a, const void *b)
{
	oaie x=*(oaie*)a,y=*(oaie*)b;
	if (x.timp>y.timp) return 1;
	if (x.timp<y.timp) return -1;
	return 0;	
}

inline void getstuff()
{
	int i; long long dMax=0,dInc=0,D=0;
	
	scanf("%d%lld%lld",&N,&dMax,&dInc);
	
	for (i=1; i<=N; ++i)
	{
		scanf("%lld%lld",&D,&A[i].lana);
		if (D>dMax) A[i].timp=0;
		else A[i].timp = (dMax - D)/dInc + 1;
		if (A[i].timp > tMax) tMax=A[i].timp;		
	}
	
	qsort(A+1,N,sizeof(A[0]),CMP);
}

inline void hmmstuff()
{
	priority_queue<long long> chestie;
	long long k=0; int i=0;
	
	for (k=tMax,i=N; k>=1; --k)
	{
		while (A[i].timp==k && i>=1)
		{	chestie.push(A[i].lana); --i;	}
		
		if (!chestie.empty())
		{	REZ+= chestie.top(); chestie.pop(); }
	}
	
	printf("%lld\n",REZ);
}

int main()
{
	freopen("lupu.in" ,"r",stdin );
	freopen("lupu.out","w",stdout);
	
	getstuff();
	hmmstuff();
	
	fclose(stdin );
	fclose(stdout);
	return 0;
}