Cod sursa(job #1146289)

Utilizator ELHoriaHoria Cretescu ELHoria Data 18 martie 2014 20:49:27
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>

using namespace std;

int main()
{

	ifstream cin("lupu.in");
	ofstream cout("lupu.out");
	int n, x, l;
	cin >> n >> x >> l;
	int d, a;
	long long ret = 0;
	vector< vector<int> > sheep(n, vector<int>());
	vector<int> bst(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> d >> a;
		if (d > x) continue;
		int steps = (x - d) / l;
		if (steps >= n) {
			ret += a;
		}
		else {
			sheep[steps].push_back(a);
		}
	}

	priority_queue<int> q;

	for (int i = n - 1; i >= 0; i--) {
		for (int k = 0; k < (int)sheep[i].size(); k++) {
			q.push(sheep[i][k]);
		}

		if (!q.empty()) {
			ret += q.top();
			q.pop();
		}
	}


	cout << ret << "\n";
	return 0;
}