Cod sursa(job #439368)

Utilizator alin.predoiAlin Predoi alin.predoi Data 11 aprilie 2010 15:41:58
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.69 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 max = i,l,r;
	l = left(i);
	r = right(i);
	if (l < dim && heap[l] > heap[i]) {
		max = l;
	}
	if (r < dim && heap[r] > max) {
		max = r;
	}
	if (max == i)	return;
	else {
		xchg (heap+i, heap+max);
		coboara (heap, dim, max);
	}
}
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)++);
}
uint scoate (uint* heap, uint *dim) {
	if (*dim == 0) return 0;
	heap[0] = heap[--(*dim)];
	uint cheie = heap[0];
	coboara (heap, *dim, 0);
	return cheie;
}


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));
		gutui[i].h = (uint) ((H - gutui[i].h )/U) + 1;
	}

	qsort (gutui, N, sizeof(gutuie), compara);
	
	uint nivel = gutui[0].h,s=0;

	for (i=0;i<N;i++) {
		while (nivel > gutui[i].h) {
			s += scoate(heap,&dim);
			nivel--;
		} 
		insert(heap, &dim, gutui[i].w);
	}
	while (nivel && dim) {
		s+=scoate(heap,&dim);
		nivel--;
	}

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