Pagini recente » Cod sursa (job #1627866) | Cod sursa (job #2870617) | Cod sursa (job #749461) | Cod sursa (job #2667183) | Cod sursa (job #1849409)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <memory>
#include <cstdio>
const int kMaxDim = (1 << 16);
const int kMaxTime = (1 << 10);
class InputReader {
public:
InputReader() {}
InputReader(const char *file_name) {
input_file = fopen(file_name, "r");
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
inline InputReader &operator >>(int &n) {
while(buffer[cursor] < '0' || buffer[cursor] > '9') {
advance();
}
n = 0;
while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
n = n * 10 + buffer[cursor] - '0';
advance();
}
return *this;
}
private:
FILE *input_file;
static const int SIZE = 1 << 17;
int cursor;
char buffer[SIZE];
inline void advance() {
++ cursor;
if(cursor == SIZE) {
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
}
};
struct Net {
Net(int _fish = 0, int _time = 0) :
fish(_fish),
time(_time) {
}
bool operator < (const Net& obj) const {
return this->time < obj.time;
}
int fish, time;
};
int netCount, maximumNets, totalTime;
int precalcMaximumFishCount[kMaxTime];
long long dp[kMaxDim];
Net nets[kMaxDim];
std::priority_queue< int > heap;
int main() {
InputReader inputFile("peste.in");
std::ofstream outputFile("peste.out");
inputFile >> netCount >> maximumNets >> totalTime;
for (int i = 0; i < netCount; ++i)
inputFile >> nets[i].fish >> nets[i].time;
std::sort(nets, nets + netCount);
for (int i = 0, sum = 0; i < netCount; ++i) {
heap.push(-nets[i].fish);
sum += nets[i].fish;
while ((int)heap.size() > maximumNets) {
sum += heap.top();
heap.pop();
}
precalcMaximumFishCount[nets[i].time] = sum;
}
int maxTime = nets[netCount - 1].time;
for (int i = 1; i <= maxTime; ++i)
precalcMaximumFishCount[i] = std::max(precalcMaximumFishCount[i], precalcMaximumFishCount[i - 1]);
for (int j = 1; j <= maxTime; ++j)
for (int i = j; i <= totalTime; ++i)
dp[i] = std::max(dp[i], dp[i - j] + precalcMaximumFishCount[j]);
outputFile << dp[totalTime] << '\n';
outputFile.close();
return 0;
}
//Trust me, I'm the Doctor!