Cod sursa(job #2412379)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 22 aprilie 2019 10:36:30
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
#include<set>
#include<algorithm>
using namespace std;
ifstream in ("lupu.in");
ofstream out ("lupu.out");
int n,l,x,a,b,k,cnt,t;
long long total;
pair<int,int>oite[100005];
multiset<int> s;
int main (void) {
    in >> n >> x >> l;
    for (int i = 1; i <= n; i ++) {
        in >> a >> b;
        if (a <= x) {
            k ++;
            oite[k].first = (x - a) / l + 1;;
            oite[k].second = b;
        }
    }


    sort (oite+1,oite+k+1);

    t = oite[k].first;
    cnt = k;
    for (int i = t; i >= 1; i --) {
        while (cnt >= 1 && oite[cnt].first == i) {
            s.insert(oite[cnt].second);
            cnt --;
        }
        if (!s.empty()) {
            total += *(s.rbegin());
            s.erase(--s.end());
        }
    }
    out << total;
    return 0;
}