Pagini recente » Cod sursa (job #310706) | Cod sursa (job #1512311) | Cod sursa (job #2191573) | Cod sursa (job #1764230) | Cod sursa (job #3041136)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
const int NMAX = 100000;
struct Oaie
{
int d;
int a;
};
Oaie oi[1 + NMAX];
/// Greedy
bool comp(const Oaie& a, const Oaie& b)
{
return a.d < b.d;
}
priority_queue<int, vector<int>, greater<int>> pq;
int main()
{
ifstream in("lupu.in");
ofstream out("lupu.out");
ios_base::sync_with_stdio(false);
in.tie(nullptr);
int n, x, l;
in >> n >> x >> l;
for (int i = 1; i <= n; i++)
in >> oi[i].d >> oi[i].a;
sort(oi + 1, oi + 1 + n, comp);
long long sol = 0;
int ratie = 0;
for (int i = n; i >= 1; i--)
{
if (oi[i].d + ratie <= x)
{
sol += oi[i].a;
ratie += l;
pq.emplace(oi[i].a);
}
else if (!pq.empty() && oi[i].d + ratie - l <= x && oi[i].a > pq.top())
{
sol -= pq.top();
pq.pop();
pq.emplace(oi[i].a);
sol += oi[i].a;
}
}
out << sol << '\n';
in.close();
out.close();
return 0;
}