Pagini recente » Cod sursa (job #737098) | Cod sursa (job #772263) | Cod sursa (job #353397) | Cod sursa (job #472738) | Cod sursa (job #2040237)
#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 < int, vector < int >, greater < 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 <= n; i++) {
H.push (v[i].second);
s += v[i].second;
while (H.size () > k) {
s -= H.top ();
H.pop ();
}
aux[v[i].first] = max (s, aux[v[i].first]);
}
for (int i = 1; i <= TMAX; i++) {
for (int j = 1; j <= min (i, v[n].first); j++) {
best[i] = max (best[i], best[i - j] + aux[j]);
}
}
fout << best[TMAX];
return 0;
}