Cod sursa(job #166338)

Utilizator damaDamaschin Mihai dama Data 27 martie 2008 21:29:15
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>
#include <algorithm>

const int nm = 50010;

#define p second
#define t first

using namespace std;

pair<int, int> plasa[nm];
int v[nm], c[nm], h[nm], N, K, T, sum;

void up(int);
void down(int);

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

	int i, j;

	scanf("%d %d %d", &N, &K, &T);

	for(i = 1; i <= N; ++i)
	{
		scanf("%d %d", &plasa[i].p, &plasa[i].t);
	}

	sort(plasa + 1, plasa + N + 1);

	for(i = 1; i <= N; ++i)
	{
		if(i <= K)
		{
			h[++h[0]] = plasa[i].p;
			up(h[0]);
			sum += plasa[i].p;
		}
		else
		{
			if(plasa[i].p > h[1])
			{
				sum -= h[1];
				sum += plasa[i].p;
				h[1] = plasa[i].p;
				down(1);
			}
		}

		if(v[plasa[i].t] < sum)
		{
			v[plasa[i].t] = sum;
		}
	}
/*
	for(i = 1; i <= T; ++i)
	{
		printf("%d\n", v[i]);
	}
*/
	for(i = 1; i <= T; ++i)
	{
		for(j = 1; j <= 1000 && j <= i; ++j)
		{
			if(c[i] < c[i - j] + v[j])
			{
				c[i] = c[i - j] + v[j];
			}
		}
	}

	printf("%d\n", c[T]);

	return 0;
}

void up(int nod)
{
	if(nod != 1)
	{
		int dad = nod / 2, temp;
		if(h[nod] < h[dad])
		{
			temp = h[nod];
			h[nod] = h[dad];
			h[dad] = temp;
			up(dad);
		}
	}
}

void down(int nod)
{
	int l = 2 * nod, r = 2 * nod + 1, temp, best = nod;

	if(l <= h[0] && h[l] < h[best])
	{
		best = l;
	}
	if(r <= h[0] && h[r] < h[best])
	{
		best = r;
	}
	if(best != nod)
	{
		temp = h[best];
		h[best] = h[nod];
		h[nod] = temp;
		down(best);
	}
}