Pagini recente » Cod sursa (job #2918837) | Cod sursa (job #3149252) | Cod sursa (job #501869) | Cod sursa (job #1941569) | Cod sursa (job #1334032)
#include <fstream>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 50005;
const int MAXT = 1001;
struct peste {
int p, t;
};
peste P[MAXN];
int aux[MAXT], dp[MAXN];
bool cmp(peste a, peste b) {
if(a.t == b.t)
return a.p < b.p;
return a.t < b.t;
}
priority_queue < int, vector <int>, greater <int> > q;
int main()
{
ifstream cin("peste.in");
ofstream cout("peste.out");
int N, K, T, maxt = 0;
cin >> N >> K >> T;
for(int i = 1; i <= N; ++i) {
cin >> P[i].p >> P[i].t;
if(P[i].t > maxt)
maxt = P[i].t;
}
int s = 0;
sort(P + 1, P + N + 1, cmp);
for(int i = 1; i <= N; ++i) {
q.push(P[i].p);
s += P[i].p;
if(i > K) {
s -= q.top();
q.pop();
}
aux[P[i].t] = s;
}
for(int i = 1; i <= T; ++i) {
for(int j = 1; j <= maxt && i - j >= 0; ++j)
if(dp[i - j] + aux[j] > dp[i])
dp[i] = dp[i - j] + aux[j];
}
cout << dp[T];
return 0;
}