Cod sursa(job #2588267)

Utilizator DawlauAndrei Blahovici Dawlau Data 24 martie 2020 16:41:18
Problema Lupul Urias si Rau Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

void solve0case(int &n, const int &x) {

	long long sum = 0;
	for (; n; --n) {

		int d, c;
		fin >> d >> c;

		if (d <= x)
			sum += c;
	}

	fout << sum;
}

class heapKey {

	public:

		int c, it;

		bool operator <(const heapKey& other) const {

			if (it == other.it)
				return c < other.c;
			return it > other.it;
		}
};

int main() {

	int n, x, l;
	fin >> n >> x >> l;

	if (l == 0) {

		solve0case(n, x);
		return 0;
	}

	int maxIt = 0;
	priority_queue <heapKey, vector <heapKey> > Heap;

	for (; n; --n) {

		int d, c;
		fin >> d >> c;

		int it = (x - d) / l + 1;
		maxIt = max(maxIt, it);

		Heap.push({ c, it });
	}

	long long sum = 0;
	for (int it = 1; it <= maxIt; ++it) {

		while (!Heap.empty() and Heap.top().it < it)
			Heap.pop();

		if (!Heap.empty()) {

			sum += Heap.top().c;
			Heap.pop();
		}
	}

	fout << sum;
}