Cod sursa(job #2913570)

Utilizator mariusn01Marius Nicoli mariusn01 Data 15 iulie 2022 11:19:50
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
multiset<int> s;
vector< pair<int, int> > v;
int N, L, X, dinit, lana, i, t;
multiset<int>::iterator it;
long long sol;
int main () {
    ifstream fin ("lupu.in");
    ofstream fout("lupu.out");

    fin>>N>>X>>L;
    /// sunt N oi, pot fi prinse doar la o distanta maxim X si
    /// la fiecare pas se deplaseaza cu L

    for (int i=1;i<=N;i++) {
        fin>>dinit>>lana;
        v.push_back({(X-dinit)/L, lana});
    }
    sort(v.begin(), v.end());
    i = v.size()-1;
    for (t= v[v.size()-1].first; t >= 0; t--) {
        while (i>=0 && v[i].first >= t) {
            s.insert(v[i].second);
            i--;
        }
        if (!s.empty()) {
            it = s.end();
            it --;
            sol += *it;
            s.erase(it);
        }
    }
    fout<<sol;
    return 0;
}