Cod sursa(job #205638)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 2 septembrie 2008 11:40:32
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 50010
#define maxt 1010
#define ll long long

int n, k, m, nr;
int a[maxn], b[maxn], p[maxn];
ll c[maxn];
int best[maxt], v[maxt];

int cmp(int x, int y)
{
	return b[x] < b[y];
}

int main()
{
	freopen("peste.in", "r", stdin);
	freopen("peste.out", "w", stdout);

	scanf("%d %d %d ", &n, &k, &m);

	int i, j, x;

	for (i=1; i<=n; i++) 
	{
		scanf("%d %d ", &a[i], &b[i]);
		p[i] = i;
	}

	sort(p+1, p+n+1, cmp);

	j = x = 1;

	for (i=1; i<maxt; i++)
	{
		best[i] = best[i-1];

		for (; b[p[j]] == i; j++)
			if (a[p[j]] >= x) 
			{
				nr++;
				best[i] += a[p[j]];
				v[a[p[j]]]++;
			}

		for (; x<maxt && nr>k; )
			if (v[x])
			{
				best[i] -= x;
				v[x]--, nr--;
			}
			else x++;
	}

	for (i=0; i<=m; i++)
		for (j=1; j<maxt && i+j<=m; j++) c[i+j] = max(c[i+j], c[i] + best[j]);

	printf("%lld\n", c[m]);

	return 0;
}