Cod sursa(job #3194397)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 17 ianuarie 2024 20:59:41
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

const int Nmax = 100005;

pair<int, int> oi[Nmax];
priority_queue<int> pq; // oile pe care le pot manca la fiecare moment T

int main() {
    int n, x, l;
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    fin >> n >> x >> l;
    for(int i = 1; i <= n; i++) {
        int dist, lana;
        fin >> dist >> lana;
        oi[i] = {(x - dist) / l, lana};
    }
    sort(oi + 1, oi + n + 1);
    int p = n;
    long long sol = 0;
    for(int i = n; i >= 1; i--) {
        if(i < n && oi[i].first == oi[i + 1].first) {
            continue;
        }

        // Sunt la momentul nou de timp T = oi[i].first
        int T = oi[i].first, T1 = oi[i + 1].first;

        // 1) Aleg oile maxime pt momentele de timp [T+1, T1)
        int momente = T1 - T - 1;
        while(momente && !pq.empty()) {
            sol += pq.top();
            pq.pop();
            momente--;
        }

        // 2) Adaug in pq toate oile noi care pot fi mancate
        while(p >= 1 && oi[p].first >= T) {
            pq.push(oi[p].second);
            p--;
        }

        // Aleg oaia maxima pt mom de timp T
        sol += pq.top();
        pq.pop();
    }

    // Aleg oile intre momentele [0, oi[1].first)
    int momente = oi[1].first - 1;
    while(momente && !pq.empty()) {
        sol += pq.top();
        pq.pop();
        momente--;
    }
    fout << sol << "\n";
    return 0;
}