Cod sursa(job #1849440)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 17 ianuarie 2017 16:00:54
Problema Peste Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

FILE *fin  = fopen("peste.in", "r");
FILE *fout = fopen("peste.out", "w");

const int kMaxDim = 50005;
const int kMaxTime = 1005;
const int kBuffMax = 100000;

char buff[kBuffMax];
int pp;
int Read() {
	int val = 0;
	while (!(buff[pp] >= '0' && buff[pp] <= '9')) {
		pp++;
		if (pp == kBuffMax) {
			fread(buff, 1, kBuffMax, fin);
			pp=0;
		}
	}
	while (buff[pp] >= '0' && buff[pp] <= '9') {
		val = val*10 + buff[pp] - '0';
		pp++;
		if (pp == kBuffMax) {
			fread(buff, 1, kBuffMax, fin);
			pp=0;
		}
	}
	return val;
}

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;
	netCount = Read(); maximumNets = Read(); totalTime = Read();
	for (int i = 1; i <= netCount; ++i) {
		nets[i].fish = Read();
		nets[i].time = Read();
	}

	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]);

	fprintf(fout, "%lld\n", dp[totalTime]);

	return 0;
}

//Trust me, I'm the Doctor!