Cod sursa(job #3166982)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 9 noiembrie 2023 20:57:26
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

const int Nmax = 100000;

priority_queue<int> q;

struct Oaie {
    int lana, timp;
    bool operator < (const Oaie &o) {
        return timp < o.timp;
    }
};
Oaie oi[Nmax];

int main() {
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");

    int n, x, l, dist, p, t;
    long long sol;

    fin >> n >> x >> l;
    for(int i = 0; i < n; i++) {
        fin >> dist >> oi[i].lana;
        oi[i].timp = (x - dist) / l;
    }

    sort(oi, oi + n);

    p = n - 1;
    t = oi[n - 1].timp;
    sol = 0;

    while(t >= 0) {
        while(p >= 0 && oi[p].timp >= t) {
            q.push(oi[p].lana);
            p--;
        }

        if(!q.empty()) {
            sol += q.top();
            q.pop();
        }
        t--;
    }

    fout << sol;

    return 0;
}