Cod sursa(job #487679)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 25 septembrie 2010 23:07:16
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

#include <algorithm>
#include <queue>

using namespace std;

struct vect
{
	int t, p;
};

int n, k, t;
vect v[50002];
int nr[1002], sol[50002];

priority_queue <int, vector <int>, greater <int> > heap;

inline int cmp (vect a, vect b)
{
	return a.t < b.t;
}

inline int max (int a, int b) {return a > b ? a : b;}

int main ()
{
	freopen ("peste.in", "r", stdin);
	freopen ("peste.out", "w", stdout);
	
	scanf ("%d %d %d", &n, &k, &t);
	
	int i, j, s = 0;
	
	for (i = 1; i <= n; i ++)
		scanf ("%d %d", &v[i].p, &v[i].t);
	sort (v + 1, v + n + 1, cmp);
	
	for (i = 1; i <= n; i ++)
	{
		s += v[i].p;
		heap.push (v[i].p);
		if (heap.size() > k)
		{
			s -= heap.top ();
			heap.pop ();
		}
		nr[v[i].t] = max (nr[i], s);
	}
	
	for (i = 1; i <= 1000; i ++)
		nr[i] = max (nr[i], nr[i - 1]);
	
	for (i = 1; i <= t; i ++)
		for (j = i - 1; j >= max (i - 1000, 0); j --)
			sol[i] = max (sol[i], sol[j] + nr[i - j]);
	
	printf ("%d\n", sol[t]);
	
	return 0;
}