Pagini recente » Cod sursa (job #443663) | Cod sursa (job #1427879) | Cod sursa (job #1687184) | Cod sursa (job #285537) | Cod sursa (job #1849438)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
const int kMaxDim = 50005;
const int kMaxTime = 1005;
struct Net {
int fish, time;
};
Net nets[kMaxDim];
int prec[kMaxTime];
long long dp[kMaxDim];
priority_queue< int, vector< int >, greater< int > > h;
inline bool Comp(const Net& a, const Net& b) {
if (a.time == b.time)
return a.fish < b.fish;
return a.time < b.time;
}
int main() {
int netCount, maximumNets, totalTime;
fin >> netCount >> maximumNets >> totalTime;
for (int i = 1; i <= netCount; ++i)
fin >> nets[i].fish >> nets[i].time;
sort(nets + 1, nets + netCount + 1, Comp);
int maxTime = nets[netCount].time, sum = 0;
for (int i = 1; i <= netCount; ++i) {
h.push(nets[i].fish);
sum += nets[i].fish;
if (i > maximumNets) {
sum -= h.top();
h.pop();
}
prec[nets[i].time] = sum;
}
for (int i = 1; i <= maxTime; ++i)
prec[i] = max(prec[i], prec[i - 1]);
for (int i = 1; i <= totalTime; ++i)
for (int j = 1; j <= maxTime && j <= i; ++j)
dp[i] = max(dp[i], dp[i - j] + prec[j]);
fout << dp[totalTime] << '\n';
return 0;
}
//Trust me, I'm the Doctor!