Cod sursa(job #2767307)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 5 august 2021 16:15:31
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
#define NMAX 1000003

using namespace std;

bool bigger(int a,int b) {
    return a > b;
}


template <typename T>
class heap {
private:
    vector<T> t;
    // pereche (prioritate, pufosenie);

    bool (*comp)(T a, T b);

    void upHeap(int idx) {
        while(idx > 1 && comp(t[idx], t[idx/2]) ) {
            swap(t[idx/2], t[idx]);
            idx = idx/2;
        }

    }
    void downHeap(int idx) {
        // recursiv
        int best = idx;
        if(2 * idx <= size() && comp(t[2 * idx], t[best]) ) {
            best = 2 * idx;
        }
        if(2 * idx + 1 <= size() && comp(t[2 * idx + 1],t[best] )) {
            best = 2 * idx + 1;
        }
        if(best != idx) {
            swap(t[best], t[idx]);
            downHeap(best);
        }
    }
public:
    int size() {
        return (int)t.size() - 1;
    }
    heap(bool (* f)(T a, T b) ) {
        t.resize(1);
        comp = f;
    }
    void insert(T val) {
        t.push_back(val);
        upHeap(size());
    }
    void pop() {
        swap(t[1], t[size()]);
        t.pop_back();
        downHeap(1);
    }
    T top() {
        return t[1];
    }

};

int n, x, l;
vector<pair<int,int> > v;

int main() {
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d %d %d",&n,&x,&l);
    int hmax = 0;
    for(int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d %d",&a,&b);
        if(a <= x) {
            v.push_back({(x - a)/l, b});
            hmax = max(hmax, (x - a)/l);
        }
    }
    sort(v.rbegin(), v.rend());
    heap<int> h(bigger);
    int sol = 0;
    int idx = 0;
    for(int i = hmax; i >= 0; i--) {
        while(idx < v.size() && v[idx].first == i) {
            h.insert(v[idx++].second);
        }
        if(h.size() > 0) {
            sol += h.top();
            h.pop();
        }
    }


    printf("%d",sol);


    return 0;
}