Cod sursa(job #553504)

Utilizator toniobFMI - Barbalau Antonio toniob Data 14 martie 2011 09:26:16
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <queue>
using namespace std;

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

const int N = 1 << 17;
int n, x, l, timp;
long long sol;
pair <int, int> v[N];
priority_queue <int, vector <int>, greater <int> > heap;

void citire () {
	in >> n >> x >> l;
	for (int i = 1; i <= n; ++i) {
		in >> v[i].first >> v[i].second;
		v[i].first = -v[i].first;
	}
}

void exe () {
	sort (v + 1, v + n + 1);
	for (int i = 1; i <= n; ++i) {
		v[i].first = -v[i].first;
	}
	
	for (int i = 1; i <= n; ++i) {
		if (timp * l + v[i].first <= x) {
			heap.push (v[i].second);
			sol += v[i].second;
			++timp;
		} else {
			if (!heap.empty() && v[i].second > heap.top ()) {
				sol -= heap.top ();
				sol += v[i].second;
				heap.pop ();
				heap.push (v[i].second);
			}
		}
	}
}

void afisare () {
	out << sol << '\n';
}

int main () {
	citire ();
	
	exe ();
	
	afisare ();
	
	return 0;
}