Pagini recente » Rating Nastase Alexandru (qusy) | Cod sursa (job #2004972) | Cod sursa (job #3268314) | Cod sursa (job #2306618) | Cod sursa (job #2040241)
#include <fstream>
#include <queue>
#include <algorithm>
#define DEF 50005
using namespace std;
ifstream fin ("peste.in");
ofstream fout ("peste.out");
int n, k, TMAX;
long long s, aux[DEF], best[DEF];
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;
}
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 = 0; j <= min (i, v[n].first); j++) {
best[i] = max (best[i], best[i - j] + aux[j]);
}
}
fout << best[TMAX];
return 0;
}