Cod sursa(job #438038)

Utilizator dragos.denaDena Dragos dragos.dena Data 10 aprilie 2010 14:01:24
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.3 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stdint.h>

#define INDEX(h)  (((H)/(U)) - ((H - (h))/U)) 		// nivelul in care intra o anumita gutaie in functie de inaltime
#define LEVELS    ((H/U) + 1)						// numarul de nivele in functie de inaltimea maxima si diferenta dintre 
													// nivele

using namespace std;
uint32_t N, H, U;		// Numarul de Gutui, Inaltimea maxima, Pasul de inaltare
ifstream in ("gutui.in");
ofstream out ("gutui.out");

typedef struct _iter_info
{
	uint32_t max;
	uint32_t index;
} IterInfo, *PIterInfo;

class Level {
	private:
		vector<uint32_t> data;
		uint32_t crt_max;

	public:
		void add_gut(uint32_t g);
		void partial_sort_(uint32_t n);
		uint32_t max();
		uint32_t get_max();
};

bool compare_g(uint32_t g1, uint32_t g2) { return (g1 < g2); }

int main()
{
	in >> N >> H >> U;
	
	uint32_t sum = 0;
	const uint32_t max_sorted = ( N > LEVELS ) ? LEVELS : N;
	uint32_t temp_g, temp_h;
	Level* levels = new Level[LEVELS];
	for(uint32_t i = 0; i < N; i ++)
	{
		in >> temp_h >> temp_g;
		levels[INDEX(temp_h)].add_gut(temp_g);
	}

	for(uint32_t i; i < LEVELS; i ++)
		levels[i].partial_sort_(max_sorted - i);

	PIterInfo iter_info = new IterInfo[LEVELS];
	uint32_t temp_max;
	iter_info[0].max = levels[0].max();
	iter_info[0].index = 0;
	for(uint32_t i = 0; i < LEVELS; i ++)
	{
		temp_max = levels[i].max();
		if(temp_max > iter_info[i - 1].max)
		{
			iter_info[i].max = temp_max;
			iter_info[i].index = i;
		}
		else
		{
			iter_info[i].max = iter_info[i - 1].max;
			iter_info[i].index = iter_info[i - 1].index;
		}
	}
/*
	for(uint32_t i = 0; i < LEVELS; i ++)
	{	
		sum += 
	}*/
	//vector<Gut> gutui (gut, gut + N);
	// vector<Gut>::iterator gut_iter;
	// sort(gutui.begin(), gutui.end(), compare_lvl);

	//PLvlInfo lvl_info = new LvlInfo[LEVELS];
	//for
	//for(int i = 0; i < LEVELS; i ++)
	//	partial_sort(gutui.begin(), gutui.begin() + max_sorted, gutui.end(), compare_lvl);
	out << sum;
	return 0;
}

void Level::add_gut(uint32_t g)
{
	data.push_back(g);
}

void Level::partial_sort_(uint32_t n)
{
	partial_sort(data.begin(), data.begin() + n, data.end(), compare_g);
	crt_max = 0;
}

uint32_t Level::max()
{
	if(data.size() == 0)
		return 0;
	return data[0];
}

uint32_t Level::get_max()
{
	if(data.size() == 0)
		return 0;
	return data[crt_max];
	crt_max ++;
}