Cod sursa(job #438050)

Utilizator mockeBarca Cristian Mihai mocke Data 10 aprilie 2010 14:16:29
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.18 kb
#include <stdio.h>

#define NMAX 100001

struct sheap {
	int v, ind;
} h[NMAX+1];

struct gutuie {
	int h, g, tmin;
} gutui[NMAX+1];

int l_heap;
int T, N, H, U;

void propaga(int vf, int nn) {
	int baza;
	
	gutuie val = gutui[vf];
	
	for (baza = 2 * vf; baza <= nn; baza *= 2) {
		if (baza < nn && gutui[baza].tmin < gutui[baza + 1].tmin) ++baza;
		if (val.tmin < gutui[baza].tmin) {
			gutui[vf] = gutui[baza];
			vf = baza;
		}
        else break;
	}
	
	gutui[vf]=val;
}

void heap() {
	int i;
	for (i = N/2; i >= 1; i--) propaga(i, N);
}

void heapsort() {
	int i;
	gutuie aux;
	
	heap();
	
	for (i = N; i > 1; i--) {
		aux = gutui[i];
		gutui[i] = gutui[1];
		gutui[1] = aux;
		propaga(1, i - 1);
	}
}

void insert_heap(int timp, int ap) {
	sheap 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) {
	sheap 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; 
    }
 
	heapsort(); 
 
	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;
}