Pagini recente » Cod sursa (job #1003710) | Cod sursa (job #2939392) | Cod sursa (job #3235412) | Cod sursa (job #2511281) | Cod sursa (job #2718935)
#include <bits/stdc++.h>
#define NMAX 50005
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
struct chestie{
int p, t;
}v[NMAX];
inline bool cmp(chestie a, chestie b){
if(a.t == b.t)
return a.p < b.p;
return a.t < b.t;
}
priority_queue<int> pq;
long long dp[NMAX], nrP[NMAX];
int main()
{
int n, k, ttotal;
fin >> n >> k >> ttotal;
for(int i = 1; i <= n; ++i)
fin >> v[i].p >> v[i].t;
sort(v + 1, v + n + 1, cmp);
long long sum = 0;
for(int i = 1; i <= n; ++i){
sum += v[i].p;
pq.push(-v[i].p);
while(pq.size() > k){
sum += pq.top();
pq.pop();
}
nrP[v[i].t] = sum;
}
for(int i = 2; i <= 1000; ++i)
nrP[i] = max(nrP[i], nrP[i - 1]);
for(int i = 1; i <= ttotal; ++i){
dp[i] = dp[i - 1];
for(int j = 1; j <= min(i, 1000); ++j)
dp[i] = max(dp[i], dp[i - j] + nrP[j]);
}
fout << dp[ttotal] << '\n';
return 0;
}