Cod sursa(job #3177206)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 28 noiembrie 2023 18:20:59
Problema Lupul Urias si Rau Scor 92
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
const int N = 1e5 + 5;

struct oaie {
    int tmp, w;
};

int n, x, l;
long long ans;
priority_queue<int> que;
oaie v[N];

bool cmp(oaie a, oaie b) {
    return a.tmp > b.tmp;
}

int main()
{
    in >> n >> x >> l;
    for(int i=1; i<=n; i++) {
        int a, b;
        in >> a >> b;
        v[i].w = b;
        v[i].tmp = (x - a) / l + 1;
    }

    sort(v+1, v+n+1, cmp);

    v[n+1].tmp = 0;
    for(int i=1; i<=n; i++) {
        int j = i;
        while(j <= n && v[j].tmp == v[i].tmp) {
            que.push(v[j].w);
            j++;
        }

        int del = v[i].tmp - v[j].tmp;
        while(del && !que.empty()) {
            del--;
            ans += 1LL * que.top();
            que.pop();
        }

        i = j - 1;
    }

    out << ans;
    return 0;
}