Cod sursa(job #441581)

Utilizator TabaraTabara Mihai Tabara Data 12 aprilie 2010 23:24:28
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.82 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;
	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;
	H.push_back (V[0]);
	push_heap( H.begin(), H.end(), cmp2);

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

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

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

	return 0;
}