Cod sursa(job #2913617)

Utilizator mariusn01Marius Nicoli mariusn01 Data 15 iulie 2022 15:36:53
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
vector<pair<int, int> > v;
multiset<int> s;
long long sol;
int N, X, L, distanta, valoare, i, t;
multiset<int>::iterator it;
int main () {
    ifstream fin ("lupu.in");
    ofstream fout("lupu.out");
    fin>>N>>X>>L;
    for (int i=1;i<=N;i++) {
        fin>>distanta>>valoare;
        /// ultimul moment la care mai poate fi prinsa aceasta oaie
        v.push_back({(X-distanta)/L, valoare});
    }

    sort( v.begin(), v.end() ); /// sorteaza crescator dupa ultimul moment in care poate fi capturata

    /// parcurg momentele de timp de la cel mai mare posibil pana la 0
    /// ma bazez pe faptul ca daca la ultimul moment de timp pot alege doar
    /// de exemplu din doua oite, pe cea nealeasa o voi pastra in multimea
    /// de candidati si o iau in calcul la momente de timp anterioare
    /// ESENTIAL: aleg in ordine inversa a momentelor de timp
    i = v.size()-1;
    for (t = v[ v.size()-1 ].first  ; t>=0; t--) {
        /// iau descrescator toate momentele de timp relevante
        while (i >= 0 && v[i].first >= t) {
            s.insert(v[i].second);
            i--;
        }
        /// in acest moment am in s lista candidatilor sa fie alesi la momentul t
        /// aceasta lista o tin ca un set dupa costuri pentru ca voi alege
        /// elementul cu costul maxim, il sterg iar celelalte raman candidate
        /// pentru valori t urmatoare (deoarece t scade first-ul lor va fi in continuare mai mare ca t)

        if (!s.empty()) {
            it = s.end();
            it--;

            sol += *it;
            s.erase(it);

        }
    }

    fout<<sol;
}