Cod sursa(job #3178017)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 30 noiembrie 2023 20:06:13
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <queue>

#define int long long

using namespace std;

const int nmax = 1e5;
pair<int, int> a[5 + nmax];

signed main() {
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    int n, x, l;
    fin >> n >> x >> l;
    for (int i = 1; i <= n; i++) {
        int d;
        fin >> d >> a[i].first;
        a[i].second = (x - d) / l;
    }
    sort(a + 1, a + n + 1, [&](pair<int, int> a, pair<int, int> b) {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second < b.second;
    });
    priority_queue<int> pq;
    int ptr = n, ans = 0;
    for (int i = a[n].second; i >= 0; i--) {
        while (ptr >= 1 && a[ptr].second >= i) {
            pq.push(a[ptr].first);
            ptr--;
        }
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
    fout << ans << '\n';
    return 0;
}