Cod sursa(job #848239)

Utilizator arrayAnghel Mihai array Data 5 ianuarie 2013 01:34:13
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");
class cmp
{
public:
	inline bool operator()(const pair<int, int> &A, const pair<int, int> &B)
	{
		return A.first > B.first;
	}
	//inline bool operator()(const int &A, const int &B)
	//{
	//	return A < B;
	//}
};
int N, DMax, D, GG;
vector< pair<int, int> > A;
vector<int> H;
priority_queue<int> P;
int main()
{
	fin >> N >> DMax >> D;
	A.push_back(make_pair(0, 0));
	for (int i = 1; i <= N; ++i)
	{
		int X, Y;
		fin >> X >> Y;
		A.push_back(make_pair(X, Y));
		if (A[i].first > DMax) A[i].first = 0;
		else A[i].first = (DMax - A[i].first) / D + 1;
	}
	sort(A.begin() + 1, A.end(), cmp());
	for (int i = 1; i <= N; )
	{
		if (A[i].first == 0) break;
		//for (int foo = i; A[foo].first == A[i].first && i <= N; H.push_back(A[i].second), push_heap(H.begin(), H.end(), cmp()), ++i);
		//if (H.size()) GG += H.front(), pop_heap(H.begin(), H.end(), cmp()), H.pop_back();
		for (int foo = i; A[foo].first == A[i].first && i <= N; P.push(A[i].second), ++i);
		if (!P.empty()) GG += P.top(), P.pop();
	}
	fout << GG << '\n';
	fout.close();
	return 0;
}