Cod sursa(job #1849409)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 17 ianuarie 2017 15:17:36
Problema Peste Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#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!