Pagini recente » Cod sursa (job #8411) | Cod sursa (job #2781550) | Cod sursa (job #233360) | Cod sursa (job #665106) | Cod sursa (job #1675344)
#include <fstream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
const int UNDEF = -1;
int n, k, t;
pair<int, int> v[50002];
long long maxp[50002], din[50002];
vector<int> pq;
int main()
{
ifstream fin("peste.in");
ofstream fout("peste.out");
fin >> n >> k >> t;
for (int i = 1; i <= n; ++i)
fin >> v[i].second >> v[i].first;
sort(v + 1, v + n + 1);
for (int i = 1; i <= 50000; ++i)
maxp[i] = UNDEF;
long long ind = 1, sum = 0;
for (int i = 1; i <= n; ++i)
{
pq.push_back(v[i].second);
push_heap(pq.begin(), pq.end(), greater<int>());
sum += v[i].second;
if (pq.size() > k)
{
sum -= pq.front();
pop_heap(pq.begin(), pq.end(), greater<int>());
pq.pop_back();
}
maxp[v[i].first] = max(maxp[i], sum);
}
long long last = 0;
for (int i = 1; i <= 1000; ++i)
{
maxp[i] = max(maxp[i], last);
last = maxp[i];
}
for (int i = 1; i <= t; ++i)
for (int j = i - 1; j >= max(i - 1000, 0); --j)
din[i] = max(din[i], din[j] + maxp[i - j]);
fout << din[t];
fin.close();
fout.close();
}