Pagini recente » Cod sursa (job #699110) | Cod sursa (job #993747) | Cod sursa (job #1226792) | Cod sursa (job #1579717) | Cod sursa (job #2913615)
#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;
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()) {
multiset<int>::iterator it = s.end();
it--;
sol += *it;
s.erase(it);
}
}
fout<<sol;
}