Cod sursa(job #204704)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 26 august 2008 15:35:18
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <stdio.h>

int N, K, TTotal, v[50005], aux[1005], h1[50005], h2[50005], k1, k2, nr;

typedef struct
{
	int x, t;
} Peste;
Peste a[50005];

void swap(int &x, int &y)
{
	int t = x; x = y; y = t;
}

void urc1(int poz)
{
	if (poz / 2 >= 1)
		if (a[ h1[poz] ].t < a[ h1[poz / 2] ].t)
		{
			swap(h1[poz], h1[poz / 2]);
			urc1(poz / 2);
		}
}

void urc2(int poz)
{
	 if (poz / 2 >= 1)
		 if (a[ h2[poz] ].x > a[ h2[poz / 2] ].x)
		 {
			 swap(h2[poz], h2[poz / 2]);
			 urc2(poz / 2);
		 }
}

void cobor(int poz)
{
	int st, dr, m;
	st = poz * 2;
	dr = st + 1;

	m = poz;
	if (st <= k1) if (a[ h1[poz] ].t > a[ h1[st] ].t) m = st;
	if (dr <= k1) if (a[ h1[m] ].t > a[ h1[dr] ].t) m = dr;

	if (m != poz)
	{
		swap(h1[m], h1[poz]);
		cobor(m);
	}
}

void cobor2(int poz)
{
	int st, dr, m;
	st = poz * 2;
	dr = st + 1;

	m = poz;
	if (st <= k2) if (a[ h2[poz] ].x < a[ h2[st] ].x) m = st;
	if (dr <= k2) if (a[ h2[m] ].x < a[ h2[dr] ].x) m = dr;

	if (m != poz)
	{
		swap(h2[m], h2[poz]);
		cobor2(m);
	}
}


int main()
{
	freopen("peste.in","r",stdin);
	freopen("peste.out","w",stdout);
	
	int i, j, tmax = 0, max;
	scanf("%d %d %d", &N, &K, &TTotal);
	for (i = 1; i <= N; i++) 
	{
		scanf("%d %d", &a[i].x, &a[i].t);
		if (a[i].t > tmax) tmax = a[i].t;
		h1[++k1] = i;
		urc1(k1);
	}

	for (i = 1; i <= tmax; i++)
	{
		while (a[ h1[1] ].t == i && k1)
		{
			h2[++k2] = h1[1];
			urc2(k2);
			swap(h1[1],h1[k1]); k1--;
			cobor(1);
			nr++;
		}

		for (j = 1; j <= K && k2 >= 1; j++)
		{
			aux[i] += a[ h2[1] ].x;
			swap(h2[1],h2[k2]); k2--;
			cobor2(1);
		}

		for (j = k2 + 1; j <= nr; j++) { k2++; urc2(j); }
	}

	for (i = 1; i <= TTotal; i++)
	{
		max = 0;
		for (j = i - 1; j >= 0 && j >= i - tmax; j--)
			if (v[j] + aux[i - j] > max) max = v[j] + aux[i - j];
		v[i] = max;
	}

	printf("%d\n",v[TTotal]);
	return 0;
}