Cod sursa(job #441633)

Utilizator TabaraTabara Mihai Tabara Data 12 aprilie 2010 23:59:23
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.82 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

const long int NMAX = 100005;
const long int DIM = 1500099;
const char* in = "gutui.in";
const char* out = "gutui.out";

typedef struct {
	long int w;
	long int h;
	long int level;
} gutuie;

long int N, Hmax, U, Gmax;
vector<gutuie> V, H;

bool cmp_level (gutuie i, gutuie j)
{
	return i.level > j.level;
}

bool cmp_weight (gutuie i, gutuie j)
{
	return i.w < j.w;
}

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

	long int poz = 0, i, height, weight, cur_level, K;
	gutuie tmp;
	char buf[DIM];

	fread (buf, 1, DIM, stdin);
	#define cit(x)											\
	{														\
		x = 0;												\
		while (buf[poz] < '0')								\
		{													\
			++poz;											\
			if (poz == DIM) {								\
				fread (buf, 1, DIM, stdin); poz = 0; }		\
		}													\
		while (buf[poz] >= '0')								\
		{													\
			x = x*10 + buf[poz] - '0';						\
			if (++poz == DIM) {								\
				fread (buf, 1, DIM, stdin); poz = 0; }		\
		}													\
	}

	cit(N) cit(Hmax) cit(U)
	for (i = 0; i < N; ++i)
	{
		cit(height) cit(weight)
		tmp.h = height;
		tmp.w = weight;
		tmp.level = (Hmax - height)/U + 1;
		V.push_back (tmp);
	}

	sort ( V.begin(), V.end(), cmp_level );
	make_heap (H.begin(), H.end(), cmp_weight );
	cur_level = V[0].level;

	for (i = 0; i < N; ++i) {
		if (V[i].level != cur_level) {
			for (K = cur_level; K > V[i].level && H.size(); --K)
			{
				Gmax += H.front().w;
				pop_heap(H.begin(), H.end(), cmp_weight);
				H.pop_back();
			}
			cur_level = V[i].level;
		}
		H.push_back (V[i]);
		push_heap (H.begin(), H.end(), cmp_weight);
	}

	while ( cur_level-- > 0 && H.size() )
	{
		Gmax += H.front().w;
		pop_heap( H.begin(), H.end(), cmp_weight);
		H.pop_back();
	}

	printf ("%ld\n", Gmax);

	return 0;
}