Pagini recente » Cod sursa (job #1475442) | Cod sursa (job #757074) | Cod sursa (job #1828210) | Cod sursa (job #752389) | Cod sursa (job #1744949)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream cin("peste.in");
ofstream cout("peste.out");
const int MAXN = 50000;
const int MAXT = 1000;
struct Fishnet {
int p;
int t;
};
Fishnet v[1 + MAXN];
int sum[1 + MAXT];
long long dp[1 + MAXT];
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++)
dp[i] = max(dp[i], dp[i - j] + sum[j]);
cout << dp[t];
return 0;
}