Cod sursa(job #333287)

Utilizator Mishu91Andrei Misarca Mishu91 Data 22 iulie 2009 10:06:23
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX_N 100005

struct oaie
{
	int d, c, t;
} A[MAX_N];
int N, X, L, Maxt;
priority_queue <int> Q;

struct cmp
{
	bool operator() (const oaie &A, const oaie &B) const
	{
		return A.t > B.t;
	}
};

void citire()
{
	scanf("%d %d %d",&N, &X, &L);
	
	for(int i = 1; i <= N; ++i)
	{
		scanf("%d %d",&A[i].d, &A[i].c);
		A[i].t = (X - A[i].d) / L;
		Maxt = max(A[i].t, Maxt);
	}
}

void solve()
{
	long long Sol = 0;
	sort(A+1, A+N+1, cmp());
	
	/*for(int i = 1; i <= N; ++i)
		printf("%d %d %d\n", A[i].t, A[i].d, A[i].c);*/
	
	for(int t = Maxt, i = 1; t >= 0; --t)
	{
		while(t == A[i].t)
		{
			Q.push(A[i].c);
			++i;
		}
		if(!Q.empty())
		{
			Sol += Q.top();
			Q.pop();
		}
	}
	
	printf("%lld\n",Sol);
}

int main()
{
	freopen("lupu.in","rt",stdin);
	freopen("lupu.out","wt",stdout);
	
	citire();
	solve();
}