Cod sursa(job #438119)

Utilizator mockeBarca Cristian Mihai mocke Data 10 aprilie 2010 15:03:21
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.92 kb
/*
	Barca Cristian Mihai - 322CB
	tema1 PA - prob2: Gutui
*/

#include <stdio.h>
#include <stdlib.h>

#define NMAX 100001

typedef struct heap {
	int v, ind;
} THEAP; 

typedef struct gutuie {
	int h, g, tmin;
} TGUTUIE;


THEAP h[NMAX + 1];
TGUTUIE gutui[NMAX + 1];
int l_heap;
int T, N, H, U;

int comp (const void *a, const void *b) {
	TGUTUIE x, y;
	
	x = *(TGUTUIE *)a;
	y = *(TGUTUIE *)b;
	
	return  (x.tmin - y.tmin);
}

void insert_heap(int timp, int ap) {
	THEAP val;
	int vf, baza;
	
	l_heap++;
	h[l_heap].ind = timp;
	h[l_heap].v = ap;
	
	for (vf = l_heap, val = h[l_heap], baza = l_heap/2; baza > 0; baza /= 2) {
		if (val.v < h[baza].v) {
			h[vf] = h[baza];
			vf = baza;
		}
		else break;
	}
	
	h[vf] = val;
}
void pop_heap(int *timp) {
	THEAP val;
	int vf, baza;
	
	*timp = h[1].ind;
	h[1] = h[l_heap];
	l_heap--;
	
	for (vf = 1, val = h[1], baza = 2; baza <= l_heap; baza *= 2) {
		if (baza < l_heap && h[baza].v > h[baza + 1].v) baza++;
		if (val.v > h[baza].v) {
			h[vf] = h[baza];
			vf = baza;
		}
		else break;
	}
	
	h[vf] = val;
}
 
int main() {
	int last, i, j, k, timp;
	long long totG = 0;
	 
	freopen("gutui.in", "rt", stdin);
	freopen("gutui.out", "wt", stdout);
 
	scanf("%d %d %d", &N, &H, &U);
	
	for (i = 1; i <= N; i++) {
		scanf("%d %d", &gutui[i].h, &gutui[i].g);
		if (H < gutui[i].h) gutui[i].tmin = 0;
		else gutui[i].tmin = (H - gutui[i].h)/U + 1; 
    }
 
	qsort(gutui + 1, N, sizeof(TGUTUIE), comp);
 
	for (i = 1; i <= N && !gutui[i].tmin; i++);
 
	last = 1;
	for (; i <= N; i = j) {
		for (j = i; j <= N && gutui[j].tmin == gutui[i].tmin; j++);
		for (; last <= gutui[i].tmin; last++) insert_heap(last, 0);
		for (k = i; k < j; k++)
			if (h[1].v < gutui[k].g) {
				pop_heap(&timp);
				insert_heap(timp, gutui[k].g);
			} 
	}
	
	for (i = 1; i <= l_heap; i++) totG += h[i].v;
	printf("%lld\n", totG);
	 
	return 0;
}