Cod sursa(job #177997)

Utilizator slayer4uVictor Popescu slayer4u Data 13 aprilie 2008 23:16:02
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

long long i, j, o, t, k, n, sum, aux[1024], kn[50010];
multiset <long> h;

struct lol
{
	long a, b;
};
lol x[50010];

int cmpf(lol a, lol b)
{
	if (a.b != b.b)
		return a.b < b.b;
	return a.a > b.a;
}

int main()
{
	freopen ("peste.in", "rt", stdin);
	freopen ("peste.out", "wt", stdout);

	scanf("%ld %ld %ld", &n, &k, &t);

	for (i = 1; i <= n; ++i)
		scanf("%ld %ld", &x[i].a, &x[i].b);

	sort(x + 1, x + n + 1, cmpf);

	sum = 0;
	j = 1;
	for (i = 1; i <= 1000; ++i)
	{
		for (; j <= n && x[j].b == i; ++j)
		{
			if (h.size() < k)
				sum += x[j].a, h.insert(x[j].a);
			else
			if (x[j].a >= *h.begin())
				sum -= *h.begin(), h.erase(h.begin()), h.insert(x[j].a), sum += x[j].a;
		}
		aux[i] = sum;
	}

	o = 1000 < t ? 1000 : t;
	for (i = 1; i <= o; ++i)
	{
		if (kn[i] < aux[i])
			kn[i] = aux[i];
		for (j = 1; j <= t; ++j)
			if (kn[j] && j + i <= t)
			{
				if (kn[j + i] < kn[j] + aux[i])
					kn[j + i] = kn[j] + aux[i];
			}
	}

	i = t;
	while (!kn[i] && i)
		--i;

	printf("%ld\n", kn[i]);

	return 0;
}