Cod sursa(job #463584)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 16 iunie 2010 14:38:46
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.67 kb
/*
 * @ Copyright, 2010
 * Mihai Tabara
 * 325 CA
 * Task - Homework 1 ( Algorithm Design )
 * Time Complexity - O(N log N)
 * Memory Complexity - O ( N + DIM ) where DIM represents maximum number of characters in the input ( parsing the reading )
 * Solving Method - Dynamic Programming Behaviour implemented as Greedy Algorithm
 * Language used: C++
 * Program: gutui
 */

#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, cnt = 0;
	gutuie tmp;
	char buf[DIM];

	/* Parsing the input reading */

	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)
		/* Eliminating those quinces that initially do no have a valid height ( less than Hmax ) */
		if (height > Hmax) { cnt++; continue; }
		tmp.h = height;
		tmp.w = weight;
		tmp.level = (Hmax - height)/U + 1;	
		V.push_back (tmp);
	}
	/* Substracting the invalid quinces from the input */
	N -= cnt;

	/* Descending sorting of the quinces based on their level */
	sort ( V.begin(), V.end(), cmp_level );

	/* Building the heap */
	make_heap (H.begin(), H.end(), cmp_weight );
	cur_level = V[0].level;

	/* Cycling through every quince */
	for (i = 0; i < N; ++i) {
		if (V[i].level != cur_level) { 										/* Level changing */
			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]);													/* Otherwise, building the heap */
		push_heap (H.begin(), H.end(), cmp_weight);
	}

	/* In case there are still possible moves to make */
	while ( cur_level-- && H.size() )
	{
		Gmax += H.front().w;
		pop_heap( H.begin(), H.end(), cmp_weight);
		H.pop_back();
	}

	printf ("%ld\n", Gmax);
	return 0;
}