Cod sursa(job #163564)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 22 martie 2008 14:46:54
Problema Peste Scor 100
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 9-a Marime 1.04 kb
#include <stdio.h>
#include <string.h>

#define LL long long
#define FOR(i, a, b) for (int (i) = (a); (i) < (int)(b); ++(i))

#define MAXT 50005
#define MAXN 50005
#define MAXV 1000

int N, K, TIME;
int P[MAXN], T[MAXN];
LL maxP[MAXN];

int used[MAXV + 5];

LL bst[MAXT];

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

	scanf("%d %d %d", &N, &K, &TIME);
	FOR(i, 0, N)
		scanf("%d %d", P + i, T + i);

	FOR(i, 1, MAXV + 1)
	{
		memset( used, 0, sizeof(used) );
		maxP[i] = 0;

		FOR(j, 0, N)
			if (T[j] <= i)
				used[ P[j] ]++;

		int left = K;
		for (int k = MAXV; k >= 1 && left; k--)
		{
			if (!used[k])
				continue;

			if (used[k] <= left)
				maxP[i] += (long long)k * (long long)used[k],
				left -= used[k];
			else
				maxP[i] += (long long)k * (long long)left,
				left = 0;
		}
	}

	bst[0] = 0;
	FOR(i, 1, TIME + 1)
	{
		bst[i] = -1;
		FOR(k, 1, MAXV + 1)
		{
			if (k > i)
				break;

			if (bst[i - k] + maxP[k] > bst[i])
				bst[i] = bst[i - k] + maxP[k];
		}
	}
	printf("%lld\n", bst[TIME]);

	return 0;
}