Cod sursa(job #519253)

Utilizator mockeBarca Cristian Mihai mocke Data 4 ianuarie 2011 18:06:35
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.45 kb
/*
	Barca Cristian Mihai - 322CB
	tema1 PA - prob2: Gutui
*/

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

#define NMAX 100001

// struct pt min-heap, dupa v
// .v -> valoare/greutate, .ind -> indicator/timp pt cules 
typedef struct heap {
	int v, ind;
} THEAP; 

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

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

// fc de comp pt qsort, folosesc qsort pt sortarea cresc
// dupa timpul minim la care pot culege fiecare gutuie
// (cat de tarziu pot culege o gutuie)
int comp (const void *a, const void *b) {
	TGUTUIE x, y;
	x = *(TGUTUIE *)a;
	y = *(TGUTUIE *)b;
	return (x.tmin - y.tmin);
}

// inserare clasica in heap 
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;
}

// extragere clasica din heap 
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);
 
	// citire date de intrare
	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; 
	}
	 
	// aplicare qsort dupa tmin crescator
	qsort(gutui + 1, N, sizeof(TGUTUIE), comp);
 
	// eliminare gutui deja "expirate"
	for (i = 1; i <= N && !gutui[i].tmin; i++);
 
	// algoritm greedy + struct de date heap =>
	// complexitate O(NlogN)
	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);
			} 
	}
	
	// calcul grutate maxima totala 
	for (i = 1; i <= l_heap; i++) {
		totG += h[i].v; 
	}
	
	printf("%lld\n", totG);
	 
	return 0;
}