Cod sursa(job #3125866)

Utilizator SergetecLefter Sergiu Sergetec Data 4 mai 2023 18:21:28
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
/*
 * Lefter Sergiu - 04/05/2023
*/
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

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

priority_queue <int, vector<int>, greater<int>> pq;
vector <pair <int, int>> v;
int n, x, l;

int main() {
    in >> n >> x >> l;
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        in >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end(), greater <pair <int, int>>());
    int tc = 0;
    long long lTot = 0;
    for (auto p: v) {
        if (p.first + (long long)tc * l <= x) { //putem sa o mancam
            pq.push(p.second);
            lTot += p.second;
            tc++;
        } else {
            if (!pq.empty() && p.second > pq.top()) { //daca am mancat ceva pana acum si daca e mai bun decat cel mai prost
                lTot += p.second - pq.top();
                pq.pop();
                pq.push(p.second);
            }
            //altfel nu merita sa o mancam acum si nici sa o fi mancat anterior
        }
    }
    out << lTot;
    in.close();
    out.close();
    return 0;
}