Cod sursa(job #302074)

Utilizator znakeuJurba Andrei znakeu Data 8 aprilie 2009 17:16:59
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
using namespace std; 

#include <stdio.h>
#include <set>

struct oaie
{	long long lana,time; };

const int MAXN = 100005;

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.time>y.time) return 1;
	if (y.time>x.time) 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].time=0;
		else A[i].time=(dMax-D)/dInc+1;
		if (A[i].time>tMax) tMax=A[i].time;		
	}
	
	qsort(A+1,N,sizeof(A[0]),CMP);
}

inline void solve()
{
	int i;	long long k=0;
	multiset <int> chestie;
	
	for (k=1,i=1; k<=tMax && i<=N; ++k)
	{
		while (A[i].time==k && i<=N)
		{	chestie.insert(A[i].lana); ++i;	}
		
		if(!chestie.empty())
		REZ+=*chestie.rbegin();
		
		while (!chestie.empty())
			chestie.erase(chestie.begin());
	}
	
	printf("%lld\n",REZ);
	
}

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