Pagini recente » Cod sursa (job #1223296) | Cod sursa (job #811629) | Cod sursa (job #791850) | Cod sursa (job #123665) | Cod sursa (job #2823609)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
struct heapInt {
int val;
inline bool operator < (const heapInt &other) const
{
return val > other.val;
}
};
struct plasa {
int p, t;
}v[50'005];
int n, sum, pst[50'005], k, timp;
long long dp[50'005];
priority_queue <heapInt> heap;
bool cmp(plasa a, plasa b)
{
return a.t < b.t;
}
int main()
{
fin >> n >> k >> timp;
for(int i = 1; i <= n; i++)
fin >> v[i].p >> v[i].t;
sort(v + 1, v + n + 1, cmp);
for(int i = 1; i <= n; i++)
{
sum = sum + v[i].p;
heap.push({v[i].p});
if(i > k)
{
sum = sum - heap.top().val;
heap.pop();
}
pst[v[i].t] = sum;
}
for(int i = 1; i <= 1000; i++)
pst[i] = max(pst[i], pst[i - 1]);
for(int i = 1; i <= timp; i++)
{
dp[i] = dp[i - 1];
for(int j = 1; j <= i; j++)
dp[i] = max(dp[i], dp[i - j] + pst[j]);
}
fout << dp[timp] << '\n';
return 0;
}