Cod sursa(job #2915391)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 22 iulie 2022 15:41:45
Problema Lupul Urias si Rau Scor 96
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
#define NMAX 100000
#define INF 2000000009

using namespace std;

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

pair <int, int> v[NMAX];
multiset <int> s;
multiset <int> :: iterator it;

int main()
{
    register long long sum = 0;
    register int i, prev, x, l, n;

    in >> n >> x >> l;

    for (i = 0; i < n; ++i) {
        in >> v[i].first >> v[i].second;
        v[i].first = (l + x - v[i].first) / l;
    }

    sort(v, v + n);

    i = n - 1, prev = v[n - 1].first;
    while (i >= 0 && v[i].first > 0) {

        if (prev != v[i].first) {

            while (prev - v[i].first && !s.empty()) {
                it = s.begin();
                sum -= (*it);
                s.erase(it);
                --prev;
            }

            prev = v[i].first;
        }

        s.insert(-v[i].second);
        --i;
    }

    while (prev > 0 && !s.empty()) {
        it = s.begin();
        sum -= (*it);
        s.erase(it);
        --prev;
    }

    out << sum;
    return 0;
}