Cod sursa(job #437041)

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

typedef struct gutuie {
	long long int inaltime;
	long long int greutate;
} Gutuie;

int compara_inaltimi(const void * a, const void * b) {

	if ((*(Gutuie*) b).inaltime - (*(Gutuie*) a).inaltime < 0)
		return -1;
	else if ((*(Gutuie*) b).inaltime - (*(Gutuie*) a).inaltime == 0)
		return 0;
	else
		return 1;
}
void adauga_in_vector(long long int* vector, long long int size,
		long long int val) {

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

	long long 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");

	long long int nr, h_max, U, inaltime, greutate, i, iter = 0, level, *aux,
			nr_levele, cate_aleg, k;

	fscanf(fin, "%lld", &nr);
	fscanf(fin, "%lld", &h_max);
	fscanf(fin, "%lld", &U);
	Gutuie *Gutui = (Gutuie*) calloc(nr, sizeof(Gutuie));
	aux = (long long*) calloc(nr, sizeof(long long));

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

		fscanf(fin, "%lld", &inaltime);
		fscanf(fin, "%lld", &greutate);
		if (inaltime < h_max) {
			level = inaltime / U;

			if (inaltime % U == 0) {
				if (inaltime != 0) {
					level -= 1;
				}
			}
			Gutui[i].inaltime = level;
			Gutui[i].greutate = greutate;
			printf("%lld ", level);
		} else {
			iter++;
		}
	}
	nr -= iter;
	qsort(Gutui, nr, sizeof(Gutuie), compara_inaltimi);
	nr_levele = h_max / U;

	if (h_max % U != 0)
		nr_levele++;

	for (i = 0; i < nr; i++) {
		cate_aleg = nr_levele - Gutui[i].inaltime;
		if (cate_aleg > nr) {
			cate_aleg = nr;
		}
		//printf("\n cate aleg:%lld",cate_aleg);
		adauga_in_vector(aux, cate_aleg, Gutui[i].greutate);
		/*printf("\n");
		for (k = 0; k < nr; k++) {
			printf("%lld ", aux[k]);
		}*/
	}
	if (nr_levele > nr) {
		nr_levele = nr;
	}
	//printf("\nnr_levele:%lld", nr_levele);

	fprintf(fout, "%lld", suma_elem_vector(aux, nr_levele));

	return 0;
}