Cod sursa(job #1849438)

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