Pagini recente » Cod sursa (job #1124324) | Cod sursa (job #2926635) | Cod sursa (job #788279) | Cod sursa (job #1559387) | Cod sursa (job #3041139)
#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); /// Sortam crescator dupa distanta de la oaie la lup.
long long sol = 0;
int ratie = 0;
for (int i = n; i >= 1; i--)
{
if (oi[i].d + ratie <= x) /// Ideea este sa prindem mai intai oile care sunt cele mai departe (adica cele pentru care avem timp scurt de a le prinde).
{
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())
/// Daca nu mai putem prinde oi ne gandim atunci ce oaie ar fi indicat sa eliminam din submultimea aleasa pana acum
/// (adaugam in locul ei alta oaie pentru care nu e criza de timp asa mare, dar care are mai multa lana).
{
sol -= pq.top();
pq.pop();
pq.emplace(oi[i].a);
sol += oi[i].a;
}
}
out << sol << '\n';
in.close();
out.close();
return 0;
}