Cod sursa(job #2588671)

Utilizator DawlauAndrei Blahovici Dawlau Data 25 martie 2020 11:34:04
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 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;
}

int main() {

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

	if (l == 0) {

		solve0case(n, x);
		return 0;
	}

	int maxIt = 0;
	vector < pair <int, int> > Arr;
	Arr.reserve(n);

	for (int idx = 0; idx < n; ++idx) {

		int d, c;
		fin >> d >> c;
		
		int it = (x - d) / l + 1;
		if (x < d)
			it = 0;

		maxIt = max(maxIt, it);
		Arr.push_back({ it, c });
	}

	sort(Arr.begin(), Arr.end());

	long long sum = 0;
	int idx = n - 1;

	priority_queue <int, vector <int> > Heap;

	for (int it = maxIt; it >= 1; --it) {

		while (idx >= 0 and it <= Arr[idx].first)
			Heap.push(Arr[idx--].second);

		if (!Heap.empty()) {

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

	fout << sum;
}