Pagini recente » Cod sursa (job #1854145) | Cod sursa (job #1559931) | Istoria paginii runda/summer_camp_2 | Cod sursa (job #865366) | Cod sursa (job #2012199)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <memory>
const int kMaxDim = 50005;
const int kMaxTime = 1005;
class Reader {
public:
Reader(const std::string& filename) :
m_stream(filename),
m_pos(kBufferSize - 1),
m_buffer(new char[kBufferSize]) {
Next();
}
template<typename T>
Reader& operator>>(T& value) {
value = 0;
while (Current() < '0' || Current() > '9')
Next();
while (Current() >= '0' && Current() <= '9') {
value = value * 10 + Current() - '0';
Next();
}
return *this;
}
private:
const int kBufferSize = (1 << 18);
char Current() {
return m_buffer[m_pos];
}
void Next() {
if (!(++m_pos != kBufferSize)) {
m_stream.read(m_buffer.get(), kBufferSize);
m_pos = 0;
}
}
std::ifstream m_stream;
int m_pos;
std::unique_ptr<char[]> m_buffer;
};
struct Net {
bool operator < (const Net& obj) const {
return this->time < obj.time;
}
short int fish, time;
};
int netCount, maximumNets, totalTime;
int precalcMaximumFishCount[kMaxTime];
unsigned short int fr[kMaxTime];
short int f[kMaxDim], t[kMaxDim];
long long dp[kMaxDim];
Net nets[kMaxDim];
std::priority_queue< int > heap;
int main() {
Reader 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;
for (int i = 0; i < netCount; i++)
fr[nets[i].time]++;
for (int i = 1; i < kMaxTime; i++)
fr[i] += fr[i - 1];
for (int i = 0; i < netCount; i++) {
int temp = -1 + fr[nets[i].time]--;
f[temp] = nets[i].fish;
t[temp] = nets[i].time;
}
for (int i = 0, sum = 0; i < netCount; i++) {
heap.push(-f[i]);
sum += f[i];
if (i >= maximumNets) {
sum += heap.top();
heap.pop();
}
precalcMaximumFishCount[t[i]] = sum;
}
int maxTime = t[netCount - 1];
for (int i = 1; i <= maxTime; i++)
precalcMaximumFishCount[i] = std::max(precalcMaximumFishCount[i], precalcMaximumFishCount[i - 1]);
for (int i = 1; i <= maxTime; i++)
for (int j = 1; j <= i; j++)
dp[i] = std::max(dp[i], dp[i - j] + precalcMaximumFishCount[j]);
for (int i = maxTime + 1; i <= totalTime; i++)
for (int j = 1; j <= maxTime; j++)
dp[i] = std::max(dp[i], dp[i - j] + precalcMaximumFishCount[j]);
outputFile << dp[totalTime] << '\n';
outputFile.close();
return 0;
}