Pagini recente » Cod sursa (job #222215) | Cod sursa (job #1046876) | Cod sursa (job #81456) | Cod sursa (job #1373376) | Cod sursa (job #2040052)
#include <fstream>
#include <set>
#include <algorithm>
#define DEF 50001
using namespace std;
ifstream fin ("peste.in");
ofstream fout ("peste.out");
int n, k, TMAX, _i = 1, _j, aux[DEF], best[DEF], tmax;
pair < int, int > v[DEF];
multiset < pair < int, int > > S;
int main () {
fin >> n >> k >> TMAX;
for (int i = 1; i <= n; i++) {
fin >> v[i].second >> v[i].first;
tmax = max (tmax, v[i].first);
}
sort (v + 1, v + n + 1);
for (int i = 1; i <= tmax; i++) {
while (v[_i].first <= i && _i <= n) {
S.insert (make_pair ((-1) * v[_i].second, v[_i].first));
_i++;
}
_j = 0;
for (multiset < pair < int, int > >::iterator it = S.begin (); it != S.end () && _j < k; it++, _j++) {
aux[i] += (-1) * (it -> first);
}
}
for (int i = 1; i <= TMAX; i++) {
for (int j = 1; j <= i; j++) {
best[i] = max (best[i], best[i - j] + aux[j]);
}
}
fout << best[TMAX];
return 0;
}