Pagini recente » Cod sursa (job #1943133) | Cod sursa (job #946726) | Cod sursa (job #486453) | Cod sursa (job #17176) | Cod sursa (job #1157390)
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
#define maxim(a, b) ((a > b) ? a : b)
int N, K, T;
long long bst[50005], peste[1005], S;
pair<int, int> P[50005];
priority_queue<int> Q;
int main(void)
{
int i, j, min;
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
scanf("%d %d %d", &N, &K, &T);
for (i = 1; i <= N; ++i)
scanf("%d %d", &P[i].second, &P[i].first);
sort(P+1, P+N+1);
for (i = 1; i <= N; ++i)
{
if (Q.size() < (unsigned)K)
{
S += P[i].second;
Q.push(-P[i].second);
}
else
{
min = -Q.top();
if (min < P[i].second)
S = S - min + P[i].second,
Q.pop(), Q.push(-P[i].second);
}
peste[P[i].first] = S;
}
for (i = 1; i <= 1000; ++i)
if (!peste[i])
peste[i] = peste[i-1];
for (i = 1; i <= T; ++i)
for (j = 1; j <= 1000 && j <= i; ++j)
bst[i] = maxim(bst[i], bst[i-j] + peste[j]);
printf("%lld\n", bst[T]);
return 0;
}