Pagini recente » Cod sursa (job #2587861) | Cod sursa (job #2898383) | Cod sursa (job #2602066) | Cod sursa (job #1843518) | Cod sursa (job #2337074)
#include <fstream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
const int VAL=50005;
const int TMAX=1005;
int N, K, TOT, i, j, mx;
int P, T, SUM, nr[VAL];
long long dp[VAL];
multiset <int> Heap;
multiset <int> :: iterator it;
vector <int> V[TMAX];
int main()
{
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
scanf("%d %d %d", &N, &K, &TOT);
for (i=1; i<=N; i++)
{
scanf("%d %d", &P, &T);
mx=max(mx, T);
V[T].push_back(P);
}
for (i=1; i<=mx; i++)
{
for (j=0; j<V[i].size(); j++)
{
if (Heap.size()<K)
{
Heap.insert(V[i][j]);
SUM+=V[i][j];
continue;
}
it=Heap.begin();
if (*it<V[i][j])
{
SUM-=*it;
Heap.erase(it);
Heap.insert(V[i][j]);
SUM+=V[i][j];
}
}
nr[i]=SUM;
}
for (i=1; i<=TOT; i++)
for (j=max(0, i-mx); j<i; j++)
dp[i]=max(dp[i], dp[j]+nr[i-j]);
printf("%lld\n", dp[TOT]);
fclose(stdin);
fclose(stdout);
return 0;
}