Cod sursa(job #302046)

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

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

struct oaie
{	unsigned int dist,lana,time; };

const int MAXN = 100005;

oaie A[MAXN];

int N;
unsigned int dMax,dInc,tMax=0;
unsigned int 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;
	
	scanf("%d%d%d",&N,&dMax,&dInc);
	
	for (i=1; i<=N; ++i)
	{
		scanf("%d%d",&A[i].dist,&A[i].lana);
		if (A[i].dist>dMax) A[i].time=0;
		else A[i].time=(dMax-A[i].dist)/dInc+1;
		if (A[i].time>tMax) tMax=A[i].time;		
	}
	
	qsort(A+1,N,sizeof(A[0]),CMP);
}

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

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