Pagini recente » Cod sursa (job #3345199) | Cod sursa (job #3312784) | Rating Andrei Vasiloiu (VAndrew) | Cod sursa (job #776124) | Cod sursa (job #3326569)
#include <bits/stdc++.h>
using namespace std;
struct Sheep {
long long deadline; // T_i
long long wool; // A_i
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
int N;
long long X, L;
cin >> N >> X >> L;
vector<Sheep> v;
v.reserve(N);
long long answer = 0;
for (int i = 0; i < N; ++i) {
long long D, A;
cin >> D >> A;
if (D > X) {
// oaia nu poate fi atinsă niciodată
continue;
}
if (L == 0) {
// distanțele nu se schimbă, putem lua toate oile cu D <= X
answer += A;
} else {
// calculăm deadline-ul T_i = floor((X - D) / L) + 1
long long maxSteps = (X - D) / L + 1;
v.push_back({maxSteps, A});
}
}
if (L == 0) {
// deja am adunat suma pentru toate oile accesibile
cout << answer << "\n";
return 0;
}
// L > 0: aplicăm greedy cu deadline și heap minim
sort(v.begin(), v.end(), [](const Sheep& a, const Sheep& b) {
return a.deadline < b.deadline;
});
priority_queue<long long, vector<long long>, greater<long long>> pq;
long long sum = 0;
for (auto &s : v) {
sum += s.wool;
pq.push(s.wool);
// dacă avem mai multe oi alese decât ne permite deadline-ul curent
if ((long long)pq.size() > s.deadline) {
sum -= pq.top();
pq.pop();
}
}
answer = sum; // pentru L > 0, acesta e răspunsul
cout << answer << "\n";
return 0;
}