Cod sursa(job #439306)

Utilizator alin.predoiAlin Predoi alin.predoi Data 11 aprilie 2010 15:12:18
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>

#define left(i) (2*(i)+1)
#define right(i) (2*(i)+2)
#define up(i) (((i)-1)/2)

typedef unsigned int uint;
typedef struct g {
	uint h;
	uint w;
} gutuie;

void xchg (uint *a, uint *b) {
	uint aux = *a;
	*a = *b;
	*b = aux;
}

int compara (const void *a, const void *b) {
	return (*(gutuie*)b).h - (*(gutuie*)a).h;
}

void coboara (uint *heap, int dim, int i) {
	int min = i,l,r;
	l = left(i);
	r = right(i);
	if (l < dim && heap[l] < heap[i]) {
		min = l;
	}
	if (r < dim && heap[r] < min) {
		min = r;
	}
	if (min == i)	return;
	else {
		xchg (heap+i, heap+min);
		coboara (heap, dim, min);
	}
}
void urca (uint *heap, uint dim, uint i) {
	int p = up(i);
	if (i ==  0 ) return;
	if (heap[p] > heap[i])
		xchg(heap+p, heap+i);
	urca (heap, dim, p);
}
void insert (uint* heap, uint *dim, uint x) {
	heap[*dim] = x;
	urca (heap, (*dim)+1, (*dim)++);
}
void scoate (uint* heap, uint *dim) {
	heap[0] = heap[--(*dim)];
	coboara (heap, *dim, 0);
}


int main() {
	int N,H,U,i;
	uint *heap, dim=0;
	gutuie* gutui;
	freopen ("gutui.in","r",stdin);
	freopen ("gutui.out","w",stdout);

	scanf("%u %u %u", &N, &H, &U);
	gutui = (gutuie*) calloc(N,sizeof(gutuie));
	heap = (uint*) calloc(N,sizeof(uint));

	for (i=0;i<N;i++) {
		scanf("%d %d", &(gutui[i].h), &(gutui[i].w));
	}

	qsort (gutui, N, sizeof(gutuie), compara);
	insert(heap, &dim, gutui[0].w);
	H-=U;

	for (i=1;i<N;i++) {
		if (gutui[i].h > H && heap[0] < gutui[i].w) {
			scoate(heap,&dim);
			insert(heap,&dim,gutui[i].w);
		}
		if (gutui[i].h <= H) {
			insert(heap,&dim,gutui[i].w);
		}
	}
	uint s=0;
	for (i=0;i<dim;i++) {
		s+=heap[i];
	}

	printf("%u\n", s);
	return 0;
}