Cod sursa(job #204715)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 26 august 2008 16:35:45
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <stdio.h>

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

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;
	long long max, sum = 0;
	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);
	}

	k2 = K;

	for (i = 1; i <= tmax; i++)
	{
		while (a[ h1[1] ].t == i && k1)
		{
			if (a[ h1[1] ].x > a[ h2[1] ].x)
			{
				sum -= a[ h2[1] ].x;
				sum += a[ h1[1] ].x;
				h2[1] = h1[1];
				swap(h1[1],h1[k1]);
				k1--;
				cobor(1);
				cobor2(1);
			}
			else 
			{
				swap(h1[1],h1[k1]);
				k1--;
				cobor(1);
			}

		}
		aux[i] = sum;		
	}

	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("%lld\n",v[TTotal]);
	return 0;
}