Cod sursa(job #436849)

Utilizator Mihai_OrtelecanOrtelecan Mihai Alexandru Mihai_Ortelecan Data 9 aprilie 2010 00:06:40
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.81 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, care_level;
	long long i,j;

	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++) {
		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 (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]);
			}
		}
	}
	fprintf(fout, "%u\n", suma_elem_vector(rez, nr_level));

	return 0;
}