Pagini recente » Cod sursa (job #2564822) | Cod sursa (job #1000983) | Cod sursa (job #225833) | Cod sursa (job #704117) | Cod sursa (job #2097863)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 5e4;
const int MAXT = (int) 1e3;
pair <int, int> v[MAXN + 1];
int best[MAXT + 1];
multiset <int> mst;
int dp[MAXN + 1];
int main() {
ifstream cin("peste.in");
ofstream cout("peste.out");
int i, n, k, total, j;
ios::sync_with_stdio(false);
cin >> n >> k >> total;
for(i = 1; i <= n; i++) {
cin >> v[i].second >> v[i].first;
}
sort(v + 1, v + n + 1);
int p = 1;
int sum = 0;
for(i = 1; i <= MAXT; i++) {
while(p <= n && v[p].first <= i) {
if(mst.size() < k) {
mst.insert(v[p].second);
sum += v[p].second;
}
else if(v[p].second > *mst.begin()) {
sum += v[p].second - *mst.begin();
mst.erase(mst.begin());
mst.insert(v[p].second);
}
p++;
}
best[i] = sum;
}
for(i = 1; i <= total; i++) {
for(j = 1; j <= min(i, MAXT); j++) {
dp[i] = max(dp[i], dp[i - j] + best[j]);
}
}
cout << dp[total];
cin.close();
cout.close();
return 0;
}