Pagini recente » Cod sursa (job #2780977) | Cod sursa (job #182636) | Cod sursa (job #1265913) | Cod sursa (job #2517802) | Cod sursa (job #2776867)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
std::vector<std::pair<long long, long long>> v;
bool compare(const std::pair<long long, long long>& left,
const std::pair<long long, long long>& right) {
if (left.first != right.first) return left.first < right.first;
return left.second > right.second;
}
int main()
{
std::ifstream in("lupu.in");
std::ofstream out("lupu.out");
long long n, max, step;
in >> n >> max >> step;
for (int i = 1; i <= n; ++i) {
long long init, lana;
in >> init >> lana;
long long max_step = (init > max) ? 0 : ((max - init) / step);
v.push_back(std::make_pair(max_step, lana));
}
std::sort(v.begin(), v.end(), compare);
std::priority_queue<long long,
std::vector<long long>,
std::greater<long long>> picked;
step = 0;
for (int i = 0; i < v.size(); ++i) {
if (v[i].first >= step) {
// If you can pick it, just pick it.
picked.push(v[i].second);
step++;
} else {
// If you can replace something from earlier, do.
if (!picked.empty() && picked.top() < v[i].second) {
picked.pop();
picked.push(v[i].second);
}
}
}
long long sol = 0;
while (!picked.empty()) {
sol += picked.top();
picked.pop();
}
out << sol << std::endl;
return 0;
}