Cod sursa(job #437844)

Utilizator Mihai_OrtelecanOrtelecan Mihai Alexandru Mihai_Ortelecan Data 10 aprilie 2010 08:08:51
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.57 kb
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef long long int LLI;
typedef struct gutuie {
	long long int inaltime;
	long long int greutate;
} Gutuie;
typedef long long int heap[100001];

LLI father(LLI nod) {
	return nod / 2;
}
LLI left_son(LLI nod) {
	return nod * 2;
}
LLI right_son(LLI nod) {
	return nod * 2 + 1;
}
LLI min(heap H) {
	return H[1];
}
void filtreaza(heap H, LLI N, LLI K) {
	LLI key = H[K];

	while ((K > 1) && (key < H[father(K)])) {
		H[K] = H[father(K)];
		K = father(K);
	}

	H[K] = key;
}
void insert(heap H, LLI N, LLI key) {
	H[++N] = key;
	filtreaza(H, N, N);
}
void swap(heap H, LLI k, LLI son) {
	LLI aux = H[k];
	H[k] = H[son];
	H[son] = aux;
}
void sift(heap H, LLI N, LLI K) {
	LLI son;
	do {
		son = 0;
		if (left_son(K) <= N) {
			son = left_son(K);
			if (right_son(K) <= N && H[right_son(K)] < H[left_son(K)]) {
				son = right_son(K);
			}
			if (H[son] >= H[K]) {
				son = 0;
			}
		}

		if (son) {
			swap(H, K, son);
			K = son;
		}
	} while (son);
}
void cut(heap H, int N, int K) {
	H[K] = H[N];
	--N;

	if ((K > 1) && (H[K] < H[father(K)])) {
		filtreaza(H, N, K);
	} else {
		sift(H, N, K);
	}
}

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;
}

int main() {

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

	long long int nr, U, greutate, i, level = 0, nr_levele = 0, cate_aleg = 0,
			inaltime, h_max, size_of_heap = 0, raspuns = 0;
	heap H;
	int k;
	fscanf(fin, "%lld", &nr);
	fscanf(fin, "%lld", &h_max);
	fscanf(fin, "%lld", &U);
	Gutuie *Gutui = (Gutuie*) calloc(nr, sizeof(Gutuie));

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

	for (i = 0; i < nr; i++) {
		fscanf(fin, "%lld", &inaltime);
		fscanf(fin, "%lld", &greutate);

		if (inaltime > h_max) {
			level = 0;
		} else {
			level = (h_max - inaltime) / U + 1;
		}
		Gutui[i].inaltime = level;
		Gutui[i].greutate = greutate;
	}
	qsort(Gutui, nr, sizeof(Gutuie), compara_inaltimi);

	for (i = nr - 1; i >= 0; i--) {
		cate_aleg = Gutui[i].inaltime;
		if (cate_aleg > nr) {
			cate_aleg = nr;
		}
		if (cate_aleg > size_of_heap) {
			insert(H, size_of_heap, Gutui[i].greutate);
			size_of_heap++;
			raspuns += Gutui[i].greutate;
		} else {
			if (min(H) < Gutui[i].greutate) {
				raspuns -= min(H);
				cut(H, size_of_heap, 1);
				insert(H, size_of_heap - 1, Gutui[i].greutate);
				raspuns += Gutui[i].greutate;
			}
		}
	}
	fprintf(fout, "%lld", raspuns);
	return 0;
}