Cod sursa(job #486221)

Utilizator darrenRares Buhai darren Data 20 septembrie 2010 19:28:46
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

const int UNDEF = -1;

int n, k, t;
pair<int, int> v[50002];
int maxp[50002], din[50002];
vector<int> pq;

int main()
{
	ifstream fin("peste.in");
	ofstream fout("peste.out");

	fin >> n >> k >> t;
	for (int i = 1; i <= n; ++i)
		fin >> v[i].second >> v[i].first;
	sort(v + 1, v + n + 1);

	for (int i = 1; i <= 50000; ++i)
		maxp[i] = UNDEF;

	int ind = 1, sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		pq.push_back(v[i].second);
		push_heap(pq.begin(), pq.end(), greater<int>());

		sum += v[i].second;

		if (pq.size() > k)
		{
			sum -= pq.front();
			pop_heap(pq.begin(), pq.end(), greater<int>());
			pq.pop_back();
		}

		maxp[v[i].first] = max(maxp[i], sum);
	}

	int last = 0;
	for (int i = 1; i <= 1000; ++i)
	{
		maxp[i] = max(maxp[i], last);
		last = maxp[i];
	}

	for (int i = 1; i <= t; ++i)
		for (int j = i - 1; j >= max(i - 1000, 0); --j)
			din[i] = max(din[i], din[j] + maxp[i - j]);

	fout << din[t];

	fin.close();
	fout.close();
}