Cod sursa(job #1322119)

Utilizator fhandreiAndrei Hareza fhandrei Data 19 ianuarie 2015 19:43:16
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 0.93 kb
// FMI - Grupa 135 - Semigrupa 2 - Hareza Andrei
// Include
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;

// Definitii
#define pii pair<int, int>

// Constante
const int sz = 100001;

// Variabile
ifstream in("lupu.in");
ofstream out("lupu.out");

int num, maxDist, jump;
int sum;
pii sheep[sz];
priority_queue<int> heap;

// Main
int main()
{
	in >> num >> maxDist >> jump;
	
	for(int i=1 ; i<=num ; ++i)
	{
		in >> sheep[i].first >> sheep[i].second;
		if(sheep[i].first > maxDist)
			--i, --num;
	}
	
	sort(sheep+1, sheep+num+1, greater<pii>());
	
	for(int currentRange=(maxDist%jump)+1-jump ; currentRange<=maxDist ; currentRange+=jump)
	{
		while(num && sheep[num].first < currentRange+jump)
			heap.push(sheep[num--].second);
		
		if(heap.empty())
			continue;
		sum += heap.top();
		heap.pop();
	}
	
	out << sum << '\n';
	
	in.close();
	out.close();
	return 0;
}