Cod sursa(job #435620)

Utilizator lucia.rosculeteLucia Rosculete lucia.rosculete Data 7 aprilie 2010 18:09:43
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.61 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int h,u, rest;


typedef struct height_weight_fruit {
	int height;
	int weight;
} fruit;


int tree_level (int height) {
	return (height-rest)/u;
}

bool compare_fruits (fruit f1, fruit f2) {
	if (tree_level(f1.height) == tree_level(f2.height))
		return (f1.weight > f2.weight);	
	return (tree_level(f1.height) > tree_level(f2.height));
}

int left (int i) {
	int son = 2*i +1;
	return son;
}

int right (int i) {
	int son = 2*i +2;
	return son;
}

int parent (int i, int n) {
	int father = (i-1)/2;
	if (father < 0)
		return -1;
	return father;
}

void restore_heap (int pos, int *v, int n) {
	int desc;
	while (1) {
		int max = v[pos];
		if ( left(pos) < n && v[left(pos)] > max )
			max = v[left(pos)];
		if ( right(pos) < n && v[right(pos)] > max )
			max = v[right(pos)];
		if (max == v[pos])
			return ;
		if ( left(pos) < n && max == v[left(pos)]) {
			desc = left(pos);
		}		
		else {
			desc = right(pos);
		}
		// interschimb valori pos, desc
		int aux = v[pos];
		v[pos] = v[desc];
		v[desc] = aux;
		pos = desc;
	}
}


void make_heap (int *v, int n) {
	for (int i=n/2; i>=0; i--) {
		restore_heap(i, v, n);
	}
}

int get_max (int *heap, int *n){
	int max = heap[0];
	heap[0] = heap[*n-1];
	heap[*n-1] = max;
	(*n) --;
	restore_heap (0, heap, *n);
	return max;
}
int main() {
	FILE *in, *out;
	in = fopen ("gutui.in", "r");
	out = fopen ("gutui.out", "w");
	
	int n;
	fruit *quince;
	
	fscanf (in, "%d %d %d", &n, &h, &u);
	rest = h%u + 1;
	quince = (fruit *)calloc(n, sizeof(fruit));
	for (int i=0; i<n; i++) {
		fscanf (in, "%d %d", &(quince[i].height), &(quince[i].weight));
	}
	
	vector<fruit> fruits (quince, quince+n);
	vector<fruit>::iterator it;

	sort (fruits.begin(), fruits.end(), compare_fruits);
	//for (it = fruits.begin (); it != fruits.end(); it++){
	//	printf ("%d %d \n", (*it).height, (*it).weight);
	//}
	it = fruits.begin();
	int	contor, index=0, max=0, max2;
	int *picked = (int *)calloc(n, sizeof(int));
	while (it != fruits.end()) {
		// pentru fiecare nivel
		picked[index] =  (*it).weight;
		max2 = picked[index++];
		int level = tree_level((*it).height);
		contor = tree_level(h) - level;
		it ++;
		int i=0;
		while (it != fruits.end() && i< contor && tree_level((*it).height) == level) {
			picked[index++] = (*it). weight;
			it ++;
			i++;
		}
		while (it != fruits.end() && tree_level((*it).height) == level) 
			it++;
	}
	make_heap (picked, index);
	int sum=0;
	for (int i=0; i<contor+1; i++) {
		//printf("%d \n", get_max(picked, &index));
		sum = sum +get_max(picked, &index);
	}
	fprintf(out, "%d\n", sum);
	fclose (in); fclose (out);
	return 0;
}