Cod sursa(job #3347202)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 15 martie 2026 19:50:05
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
#define ll long long
#define int long long

using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int NMAX = 1e5;

int n, x, l;
ll answer;
pair<int, int> a[NMAX + 1];
vector<int> v;
vector<int> vec[NMAX + 1];
priority_queue<int> pq;

signed main() {
    fin >> n >> x >> l;
    for(int i = 1; i <= n; i++) {
        int d, c;
        fin >> d >> c;
        a[i] = {d, c};
    }

    for(int i = 1; i <= n; i++) {
        auto [d, c] = a[i];
        if(x - d >= 0) {
            int k = (x - d) / l;
            v.push_back(k);
        }
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 1; i <= n; i++) {
        auto [d, c] = a[i];
        if(x - d >= 0) {
            int k = (x - d) / l;
            int pos = lower_bound(v.begin(), v.end(), k) - v.begin();
            vec[pos].push_back(c);
        }
    }

    for(int i = v.size() - 1; i >= 0; i--) {
        int dist = (i >= 1 ? v[i] - v[i - 1] : v[i] + 1);
        for(int c : vec[i]) {
            pq.push(c);
        }

        while(!pq.empty() && dist) {
            int maxi = pq.top();
            pq.pop();
            answer += maxi;
            dist--;
        }
    }
    fout << answer << '\n';
    return 0;
}