Cod sursa(job #2832221)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 13 ianuarie 2022 10:43:32
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <algorithm>
#include <fstream>

using namespace std;

struct Oaie {
    int lana, timp;
} v[100005];

int H[100005], lh;

void add(int x) {
    H[++lh] = x;
    int clh = lh;
    while (clh > 1 && H[clh / 2] < H[clh]) {
        swap(H[clh / 2], H[clh]);
        clh /= 2;
    }
}

void del() {
    swap(H[1], H[lh]);
    lh--;
    int clh = 1;
    while (1) {
        int best = clh;
        if (2 * clh <= lh && H[2 * clh] > H[best])
            best = 2 * clh;
        if (2 * clh + 1 <= lh && H[2 * clh + 1] > H[best])
            best = 2 * clh + 1;

        if (best == clh)
            break;

        swap(H[clh], H[best]);
        clh = best;
    }
}

int cmp(Oaie a, Oaie b) { return a.timp > b.timp; }

int main() {
    ifstream cin("lupu.in");
    ofstream cout("lupu.out");
    int n, x, l, dist, maxt = 0;
    cin >> n >> x >> l;
    for (int i = 1; i <= n; i++) {
        cin >> dist >> v[i].lana;
        v[i].timp = (x - dist) / l + 1;
        maxt = max(maxt, v[i].timp);
    }
    sort(v + 1, v + n + 1, cmp);
    int j = 1, suml = 0;
    for (int i = maxt; i >= 1; i--) {
        while (j <= n && v[j].timp == i)
            add(v[j++].lana);
        if (lh > 0) {
            suml += H[1];
            del();
        }
    }
    cout << suml;
    return 0;
}