Cod sursa(job #2399086)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 6 aprilie 2019 20:40:38
Problema Lupul Urias si Rau Scor 32
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <queue>
#include <utility>
#include <fstream>
#include <algorithm>

using std::pair;
using std::make_pair;

using std::sort;
using std::vector;
using std::priority_queue;

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

int main() {
    int n;
    int64_t x, l;
    fin >> n >> x >> l;

    vector<pair<int64_t, int64_t>> v(n);
    for (int i = 0; i < n; i++)
        fin >> v[i].first >> v[i].second;

    n++;
    v.push_back(make_pair(x + 1, 0));

    sort(v.begin(), v.end());
    priority_queue<int64_t> pq;

    int64_t sol = 0;
    int64_t k = x % l;

    for (int i = 0; i < n; i++)
        if (v[i].first <= k)
            pq.push(v[i].second);
        else {
            if (!pq.empty()) {
                sol += pq.top();
                pq.pop();
            }

            while (true) {
                k += l;
                if (v[i].first <= k)
                    break;
            }

            if (k > x)
                break;
            i--;
        }

    fout << sol << '\n';
    fout.close();
    return 0;
}