Cod sursa(job #419683)

Utilizator svalentinValentin Stanciu svalentin Data 17 martie 2010 20:24:22
Problema Gutui Scor Ascuns
Compilator c Status done
Runda Marime 0.8 kb
#include <stdio.h>

#define NMAX 100000
int n, H, U, h[NMAX], g[NMAX], u[NMAX] = { 0 };

int solve()
{
	int s = 0, i, j, min, nr, max, top;
	min = h[0];
	for (i = 1; i < n; i++)
		if (h[i] < min)
			min = h[i];
	nr = (H - min) / U + 1;
	top = H - U * (nr - 1);
	for (i = 0; i < nr; i++) {
//		printf("%d ", top);
		max = -1;
		for (j = 0; j < n; j++) 
			if (h[j] <= top && h[j] <= H && u[j] == 0) 
				if (max == -1 || g[j] > g[max]) 
					max = j;
		if (max != -1) {
			u[max] = 1;
			s += g[max];
#ifdef DEBUG
		printf("%d ", g[max]);
#endif                    
		}

		top += U;
	}
#ifdef DEBUG
	printf("\n");
#endif
	return s;
}

int main()
{
	int i;
	freopen("gutui.in", "rt", stdin);
	scanf("%d%d%d", &n, &H, &U);
	for (i = 0; i < n; i++)
		scanf("%d%d", &h[i], &g[i]);
	printf("%d\n", solve());
	return 0;
}