Pagini recente » Cod sursa (job #243057) | Cod sursa (job #1608967) | Cod sursa (job #1003220) | Cod sursa (job #1467460) | Cod sursa (job #2040213)
#include <fstream>
#include <queue>
#include <algorithm>
#define DEF 50001
using namespace std;
ifstream fin ("peste.in");
ofstream fout ("peste.out");
int n, k, TMAX, _i = 1, s, aux[DEF], best[DEF], tmax;
pair < int, int > v[DEF];
priority_queue < pair < int, int >, vector < pair < int, int > > > H;
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) {
H.push ( make_pair ((-1) * v[_i].second, v[_i].first));
s += v[_i].second;
_i++;
}
while (H.size () > k) {
s -= (-1) * H.top ().first;
H.pop ();
}
aux[i] = s;
}
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;
}