Cod sursa(job #436589)

Utilizator mockeBarca Cristian Mihai mocke Data 8 aprilie 2010 17:57:59
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 0.99 kb
/*
	Barca Cristian Mihai - 322CB
	tema1 PA - prob2: Gutui
*/

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

#define MAX(a, b) ((a) < (b) ? (b) : (a))
#define NMAX 100001

typedef struct gutui {
	int h, g;
} TGUTUI;

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

int main() {
	TGUTUI A[NMAX];
	int G[NMAX];
	int N, NN, H, U;
	int i, gr, hi, smax;
	int cont;
	
	freopen("gutui.in", "rt", stdin);
	freopen("gutui.out", "wt", stdout);
	
	scanf("%d %d %d", &N, &H, &U);
	
	NN = smax = 0;
	
	for (i = 1; i <= N; i++) {
		scanf("%d %d", &hi, &gr);
		if (hi <= H) {
			A[++NN].h = hi;
			A[NN].g = gr;
		}
	}
	
	qsort(A + 1, NN, sizeof(TGUTUI), comp);
	
	for (i = 1; i <= NN; i++) {
		cont = 0;
		hi = H - A[i].h;
		cont = hi/U + 1;
		
		while (cont > 0 && G[cont] != 0) cont--;
		
		if (cont != 0) {
			G[cont] = A[i].g;
			smax += G[cont];
		}
	}
	
	printf("%d\n", smax);
	
	return 0;
}