Cod sursa(job #431713)

Utilizator ooctavTuchila Octavian ooctav Data 1 aprilie 2010 12:30:26
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
// lupu.cpp : Defines the entry point for the console application.
//
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int N, X, L, T = 0;
int REZ = 0;
const int NMAX = 100009;
vector< pair<int, int> > O;

int compar(pair<int, int> a, pair<int, int> b)
{
	return a.first > b.first;
}

struct cmp
{
	bool operator()(const pair <int, int> &a, const pair <int, int> &b)const
	{
		return a.second > b.second;
	}
};
priority_queue <int ,vector< pair<int, int> > ,cmp> Q;

void citire()
{
	int timp, lana;
	scanf("%d%d%d",&N,&X,&L);
	for(int i = 1; i <= N ; i++)
	{
		scanf("%d%d", &timp, &lana);
		timp = 1 + (X - timp) / L;
		if(timp > T)
			T = timp;
		O.push_back(make_pair(timp, lana));
	}
}


void rezolva()
{
	int nr = 1;
	for(int i = 1 ; i <= T; i++)
	{
		int j = nr;
		while(O[j].first == O[nr].first)
		{
			Q.push(make_pair(O[j].first, O[j].second));
			j++;
		}
		while(1)
		{
			if(Q.top().first  <= O[nr].first)
				break;
			Q.pop();
		}
		REZ += Q.top().second;;
		nr = j;
	}
}

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	citire();
	sort(O.begin(), O.end(),compar);
	rezolva();
	printf("%d",REZ);

	return 0;
}