Pagini recente » Cod sursa (job #3267384) | Cod sursa (job #1190388) | Cod sursa (job #539195) | Cod sursa (job #718859) | Cod sursa (job #3041126)
#include <fstream>
#include <queue>
using namespace std;
struct Oaie
{
int a;
int tMax;
Oaie() = default;
Oaie(int a, int tMax) : a(a), tMax(tMax) {};
bool operator > (const Oaie& other) const
{
if (this->tMax == other.tMax)
return this->a < other.a;
return this->tMax > other.tMax;
}
};
priority_queue<Oaie, vector<Oaie>, greater<Oaie>> pq;
/// Greedy
/// Ideea e ca vrem ca oile ce nu mai pot fi prinse dupa timpul T sa le prindem cat mai aproape de acel timp final, ca sa permitem intre timp sa prindem alte oi ce scapa mai repede.
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++)
{
int d, a;
in >> d >> a;
int tMax;
if (d > x)
tMax = 0;
else if (d == x)
tMax = 1;
else
tMax = 1 + (x - d) / l;
pq.emplace(a, tMax);
}
int tCrt = 1;
long long sol = 0;
while (!pq.empty())
{
if (tCrt <= pq.top().tMax)
{
sol += pq.top().a;
pq.pop();
tCrt++;
}
else
pq.pop();
}
out << sol << '\n';
in.close();
out.close();
return 0;
}