Cod sursa(job #486210)

Utilizator darrenRares Buhai darren Data 20 septembrie 2010 19:08:16
Problema Peste Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;

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

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

	int ind = 1;
	for (int i = 1; i <= 1000; ++i)
	{
		while (v[ind].first <= i && ind <= n) pq.push(ind), ++ind;

		int sum = 0;
		for (int j = 1; j <= k && !pq.empty(); ++j)
		{
			q.push(pq.top());
			pq.pop();
			sum += v[q.back()].second;
		}
		while (!q.empty())
		{
			pq.push(q.front());
			q.pop();
		}

		maxp[i] = sum;
	}

	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();
}