Cod sursa(job #441616)

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

using namespace std;

#define NMAX 100005
#define 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 (gutuie i, gutuie j) {
	return (i.level > j.level);
}

bool cmp2 (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 );
	make_heap (H.begin(), H.end(), cmp2);
	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(), cmp2);
				H.pop_back();
			}
			cur_level = V[i].level;
		}
		H.push_back (V[i]);
		push_heap (H.begin(), H.end(), cmp2);
	}

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

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

	return 0;
}