Pagini recente » Cod sursa (job #502609) | Cod sursa (job #1989900) | Cod sursa (job #999495) | Cod sursa (job #2681375) | Cod sursa (job #1744952)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream cin("peste.in");
ofstream cout("peste.out");
const int MAXN = 50005;
const int MAXT = 1002;
struct Fishnet {
int p;
int t;
};
Fishnet v[MAXN];
int sum[MAXT];
long long dp[MAXN];
priority_queue<int, vector<int>, greater<int> > Heap;
bool Compare(const Fishnet &a, const Fishnet &b) {
if (a.t == b.t)
return a.p < b.p;
return a.t < b.t;
}
int main() {
int n, k, t, big = 0;
cin >> n >> k >> t;
for (int i = 1; i <= n; i++) {
cin >> v[i].p >> v[i].t;
if (v[i].t > big)
big = v[i].t;
}
sort(v + 1, v + n + 1, Compare);
int value = 0;
for (int i = 1; i <= n; i++) {
Heap.push(v[i].p);
value += v[i].p;
if (i > k) {
value -= Heap.top();
Heap.pop();
}
sum[v[i].t] = value;
}
for (int i = 1; i <= big; i++)
sum[i] = max(sum[i], sum[i - 1]);
for (int i = 1; i <= t; i++)
for (int j = 1; j <= big && j <= i; j++)
if (dp[i - j] + sum[j] > dp[i])
dp[i] = dp[i - j] + sum[j];
cout << dp[t];
return 0;
}