Pagini recente » Cod sursa (job #1947367) | Cod sursa (job #699277) | Monitorul de evaluare | Atasamentele paginii Profil misterjinx | Cod sursa (job #3359593)
/*
https://www.infoarena.ro/problema/lupu
*/
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct oaia
{
int dist, lana;
};
bool operator < (oaia o1, oaia o2)
{
return (o1.dist > o2.dist);
}
int main()
{
ifstream in("lupu.in");
ofstream out("lupu.out");
int n, dist_max, indepartare;
in >> n >> dist_max >> indepartare;
vector <oaia> v(n);
for (int i = 0; i < n; i++)
{
in >> v[i].dist >> v[i].lana;
}
sort(v.begin(), v.end());
int timp = 0;
long long total_lana = 0;
priority_queue <int, vector <int>, greater <int>> h_sel;
for (int i = 0; i < n; i++)
{
if (v[i].dist + timp * indepartare <= dist_max)
{
total_lana += v[i].lana;
h_sel.push(v[i].lana);
timp++;
}
else if (!h_sel.empty() && v[i].lana > h_sel.top())
{
total_lana += (v[i].lana - h_sel.top());
h_sel.pop();
h_sel.push(v[i].lana);
}
}
in.close();
out << total_lana << "\n";
out.close();
return 0;
}