Cod sursa(job #1849426)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 17 ianuarie 2017 15:38:55
Problema Peste Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <memory>
#include <cstdio>

using namespace std;

const int kMaxDim = (1 << 16);
const int kMaxTime = (1 << 10);

class Reader {
	public:
		Reader(const 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, kBufferSize);
				m_pos = 0;
			}
		}

		ifstream m_stream;
		int m_pos;
		char* m_buffer;
};

struct Net {
	int fish, time;
};

inline bool Comp(const Net& a, const Net& b) {
	return (a.time == b.time ? a.fish < b.fish : a.time < b.time);
}

int precalcMaximumFishCount[kMaxTime];
long long dp[kMaxDim];
Net nets[kMaxDim];

int main() {
	int netCount, maximumNets, totalTime;
	priority_queue< int, vector< int >, greater< int > > heap;

	Reader inputFile("peste.in");
	ofstream outputFile("peste.out");

	inputFile >> netCount >> maximumNets >> totalTime;
	for (int i = 0; i < netCount; ++i)
		inputFile >> nets[i].fish >> nets[i].time;

	sort(nets, nets + netCount, Comp);

	for (int i = 1, j = 0, sum = 0; i <= 1000; ++i) {
		for (; j < netCount && nets[j].time <= i; ++j) {
			heap.push(nets[j].fish);
			sum += nets[j].fish;
		}

		while ((int)heap.size() > maximumNets) {
			sum -= heap.top();
			heap.pop();
		}

		precalcMaximumFishCount[i] = sum;
	}

	for (int i = 1; i <= totalTime; ++i)
		for (int j = 1; j <= min(i, 1000); ++j)
			dp[i] = max(dp[i], dp[i - j] + precalcMaximumFishCount[j]);

	outputFile << dp[totalTime] << '\n';

	outputFile.close();

	return 0;
}

//Trust me, I'm the Doctor!