Cod sursa(job #436906)

Utilizator Mihai_OrtelecanOrtelecan Mihai Alexandru Mihai_Ortelecan Data 9 aprilie 2010 00:52:47
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 2.2 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void adauga_in_vector(unsigned int* vector, unsigned int size, unsigned int val) {

	unsigned int i, aux;
	for (i = 0; i < size; i++) {
		if (val >= vector[i]) {
			aux = vector[i];
			vector[i] = val;
			val = aux;
		}
	}
}
int suma_elem_vector(unsigned int* vec, unsigned int size) {

	unsigned int i, rez = 0;
	for (i = 0; i < size; i++) {
		rez += vec[i];
	}
	return rez;
}

int main() {

	FILE *fin = fopen("gutui.in", "r");
	FILE *fout = fopen("gutui.out", "w");

	unsigned int nr, h_max, U, inaltime, greutate, nr_level, *rez;
	long long i, j, care_level;

	fscanf(fin, "%u", &nr);
	fscanf(fin, "%u", &h_max);
	fscanf(fin, "%u", &U);

	nr_level = h_max / U;
	if (h_max % U != 0) {
		nr_level++;
	}

	unsigned int* alegeri_pe_nivel = (unsigned int*) calloc(h_max / U,
			sizeof(unsigned int)), *mem_aloc = (unsigned int*) calloc(nr_level,
			sizeof(unsigned int));
	for (i = 0; i < nr_level; i++) {
		if (nr_level - i > nr) {
			alegeri_pe_nivel[i] = nr;
		} else {
			alegeri_pe_nivel[i] = nr_level - i;
		}
	}

	rez = (unsigned int*) calloc(nr_level, sizeof(unsigned int));

	unsigned int** Nivel = (unsigned int**) calloc(nr_level,
			sizeof(unsigned int*));

	for (i = 1; i <= nr; i++) {

		fscanf(fin, "%d", &inaltime);
		fscanf(fin, "%d", &greutate);
		care_level = inaltime / U;
		if (inaltime % U == 0) {
			care_level -= 1;
			if (care_level == -1) {
				care_level = 0;
			}
		}
		if (mem_aloc[care_level] == 0) {
			Nivel[care_level] = (unsigned int*) calloc(
					alegeri_pe_nivel[care_level], sizeof(unsigned int));
			mem_aloc[care_level] = 1;
		}
		adauga_in_vector(Nivel[care_level], alegeri_pe_nivel[care_level],
				greutate);

	}

	for (i = nr_level - 1; i >= 0; i--) {
		for (j = 0; j < alegeri_pe_nivel[i]; j++) {
			if (mem_aloc[i] == 0) {
				break;
			} else {
				adauga_in_vector(rez, alegeri_pe_nivel[i], Nivel[i][j]);
			}
		}
	}

	/*for (i = nr_level - 1; i >= 0; i--) {
		printf("\nNivel:%lld -nr de alegeri:%u ->", i, alegeri_pe_nivel[i]);
		for (j = 0; j < alegeri_pe_nivel[i]; j++) {
			if (mem_aloc[i] == 1) {
				printf("%u ", Nivel[i][j]);
			} else {
				break;
			}
		}
	}*/

	fprintf(fout, "%u\n", suma_elem_vector(rez, nr_level));

	return 0;
}