Cod sursa(job #426475)

Utilizator adyk18enache adrian adyk18 Data 26 martie 2010 23:40:22
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.51 kb
#include <stdio.h>
#include <memory.h>
#include <malloc.h>

struct rec {
	unsigned long h;
	unsigned long w;
};

char sort(struct rec *arr, int elements, int f) {
  #define  MAX_LEVELS  1000

  struct rec piv;
	int beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R;

  beg[0] = 0; end[0]  = elements;
  while (i >= 0) {
    L = beg[i]; R = end[i]-1;
    if (L < R) {
      piv = arr[L]; 
			if (i == MAX_LEVELS-1) return 0;	//fail
      while (L < R) {
				while ((f ? arr[R].h <= piv.h : arr[R].w <= piv.w) && L < R) R--; if (L < R) arr[L++] = arr[R];
				while ((f ? arr[L].h >= piv.h : arr[L].w >= piv.w) && L < R) L++; if (L < R) arr[R--] = arr[L]; 
			}
      arr[L] = piv; beg[i+1] = L+1; end[i+1] = end[i]; end[i++] = L; 
		}
    else
      i--;
	}
  return 1;
}

int main() {
	freopen("gutui.in", "r", stdin);
	freopen("gutui.out", "w", stdout);
	int n, h, u, i;
	struct rec *arr;
	
	scanf("%d %d %d", &n, &h, &u);
	arr = (struct rec*)malloc(n * sizeof(struct rec));

	for(i = 0;i < n; i++)
		scanf("%ld %ld", &arr[i].h, &arr[i].w);

	if(!sort(arr, n, 1)) {
		//something went wrong
		return 1;
	}

	//sort equal heights by weight
	int hc = arr[0].h, st = 0;
	for(i = 1;i < n; i++) {
		for(;i < n && arr[i].h == hc; i++);
		if(i - st > 1)
			if(!sort(arr + st, i - st, 0)) {
				//sth went wrong
				return 1;
			}
		st = i;
		hc = arr[i].h;
	}

	unsigned long cdelta = 0;
	unsigned long res = 0;
	for(i = 0;i < n; i++)
		if(arr[i].h + cdelta <= h) {
			res += arr[i].w;
			cdelta += u;
		}

	printf("%ld\n", res);

	free(arr);
	return 0;
}