Pagini recente » Cod sursa (job #799788) | Cod sursa (job #1897347) | Cod sursa (job #3225315) | Cod sursa (job #2466693) | Cod sursa (job #3194396)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
const int Nmax = 100005;
pair<int, int> oi[Nmax];
priority_queue<int> pq; // oile pe care le pot manca la fiecare moment T
int main() {
int n, x, l;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
fin >> n >> x >> l;
for(int i = 1; i <= n; i++) {
int dist, lana;
fin >> dist >> lana;
oi[i] = {(x - dist) / l, lana};
}
sort(oi + 1, oi + n + 1);
int p = n;
long long sol = 0;
for(int i = n; i >= 1; i--) {
if(i < n && oi[i].first == oi[i + 1].first) {
continue;
}
// Sunt la momentul nou de timp T = oi[i].first
int T = oi[i].first, T1 = oi[i + 1].first;
// 1) Aleg oile maxime pt momentele de timp [T+1, T1)
int momente = T1 - T - 1;
while(momente && !pq.empty()) {
sol += pq.top();
pq.pop();
momente--;
}
// 2) Adaug in pq toate oile noi care pot fi mancate
while(p >= 1 && oi[p].first >= T) {
pq.push(oi[p].second);
p--;
}
// Aleg oaia maxima pt mom de timp T
sol += pq.top();
pq.pop();
}
return 0;
}