Cod sursa(job #435032)

Utilizator mockeBarca Cristian Mihai mocke Data 6 aprilie 2010 20:20:11
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.32 kb
/*
	Barca Cristian Mihai - 322CB
	tema1 PA - prob2: Gutui
*/

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

#define NMAX 100001

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

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

int cautareBin(int i, int j, int elem, TGUTUI *A, int pond) {
	int mij;
	
	while (i < j) {
		mij = (i + j)/2;
		
		if ((elem + pond) > (A[mij].h + pond)) {
			i = mij + 1;
		}
		else {
			j = mij;
		}
	}		
		
	return j;
}

int main() {
	TGUTUI A[NMAX];
	int N, H, U, i, j;
	int p1, p2, pond, max, sum, pozmax;
	
	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", &A[i].h, &A[i].g);
		A[i].cules = 0;
	}
	
	qsort(A + 1, N, sizeof(TGUTUI), comp);
	
	i = N;
	pond = max = sum = 0;
	
	while (i > 1) {
		while (A[i].h + pond > H || A[i].cules) i--;
		
		p2 = i;
		p1 = cautareBin(1, p2, A[p2].h - U, A, pond);
		
		max = -A[p1].g;
		for (j = p1; j <= p2; j++)
			if (A[j].cules == 0 && max < A[j].g) {
				max = A[j].g;
				pozmax = j;
			}				
		
		if (max > 0) {
			A[pozmax].cules = 1;
			sum += max;
		}
		
		pond = pond + U;
	}
	
	printf("%d\n", sum);
	
	return 0;
}