Cod sursa(job #438427)

Utilizator lucia.rosculeteLucia Rosculete lucia.rosculete Data 10 aprilie 2010 19:07:20
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.12 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct quince_fruit {
	int height;
	int weight;
} qfruit;

int h, u;

unsigned int get_level (int height) {
	return (h - height)/u;
}

bool compare_quinces (qfruit q1, qfruit q2) {
	if (get_level(q1.height) == get_level(q2.height))
		return (q1.weight > q2.weight);
	return (get_level(q1.height) < get_level(q2.height));
}

//return true if fisrt goes before second
bool min_heap_compare (qfruit q1, qfruit q2) {
	return (q1.weight > q2.weight);

}

int main() {
	FILE *in, *out;
	in = fopen ("gutui.in", "r");
	out = fopen ("gutui.out", "w");

	int n;
	qfruit *data;

	fscanf (in, "%d %d %d", &n, &h, &u);
	data = (qfruit *) calloc (n, sizeof(qfruit));
	for (int i=0; i<n; i++) {
		fscanf(in, "%d %d", &(data[i].height), &(data[i].weight));
	}
	vector<qfruit> fruit (data, data+n);
	vector<qfruit>::iterator it;	
	// sortare dupa nivel si greutate
	sort (fruit.begin(), fruit.end(), compare_quinces);
	//TODO afisare
	for (it=fruit.begin(); it!=fruit.end(); it++) {
		printf("%d %d\n", (*it).height, (*it).weight);
	}
	printf("\n");

	vector<qfruit> fruitheap;
	vector<qfruit>::iterator it2;	
	it = fruit.begin();
		
	while (it != fruit.end()) {
		unsigned int l = get_level ((*it).height) +1 ;
		//printf("nivel %d\n", l);
		unsigned int added =1;
		int min = 0;
		if (fruitheap.size() != 0) {
			min = (fruitheap.front()).weight;
		}
		while (get_level ((*it).height) +1 == l && it!=fruit.end()) {
			if (added <= l) {
				fruitheap.push_back (*it);
				push_heap (fruitheap.begin(), fruitheap.end(), min_heap_compare);
				added ++;
			}
			//printf ("%d \n", (*it).height);
			it ++;

		}
		while (fruitheap.size() > l) {
			pop_heap (fruitheap.begin(), fruitheap.end(), min_heap_compare);
			fruitheap.pop_back();
		}	
		//for (it2=fruitheap.begin(); it2!=fruitheap.end(); it2++) {
			//printf("%d %d\n", (*it2).height, (*it2).weight);
	
		//}

	}
	unsigned int sum =0;
	for (it=fruitheap.begin(); it!=fruitheap.end(); it++) {
		//printf("%d %d\n", (*it).height, (*it).weight);
		sum += (*it).weight;			
	}	
	fprintf (out, "%u", sum);
	fclose (in); fclose (out);
	return 0;
}