Cod sursa(job #427988)

Utilizator adyk18enache adrian adyk18 Data 28 martie 2010 17:43:05
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.24 kb
#include <stdio.h>
#include <memory.h>
#include <malloc.h>

struct rec {
	unsigned long h;
	unsigned long w;
};
struct heap {
	struct rec *v[100000];
	int len;
};

#define sw(a,b) {(a) ^= (b); (b) ^= (a); (a) ^= (b);}

void heapify(struct heap *h, int i) {
	int l = 2*i, r = 2*i+1, im;
	if(l < h->len && h->v[l]->h > h->v[i]->h)
		im = l;
	else
		im = i;
	if(r < h->len && h->v[r]->h > h->v[im]->h)
		im = r;
	if(im != i) {
		sw(h->v[i]->h, h->v[im]->h);
		sw(h->v[i]->w, h->v[im]->w);
		heapify(h, im);
	}
}

void inserth(struct heap *h, struct rec *x) {
	h->v[h->len] = x;
	int i = h->len++;
	while(h->v[i]->w > h->v[i/2]->w && i > 0) {
		sw(h->v[i]->h, h->v[i/2]->h);
		sw(h->v[i]->w, h->v[i/2]->w);
		i /= 2;
	}
}

unsigned long emaxh(struct heap *h) {
	unsigned long ret = h->v[0]->w;
	h->v[0] = h->v[--h->len];
	heapify(h, 0);
	return ret;
}

char emptyh(struct heap h) {
	return h.len == 0;
}

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

  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 (arr[R].h <= piv.h && L < R) R--; if (L < R) arr[L++] = arr[R];
				while (arr[L].h >= piv.h && 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, j;
	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("%lu %lu", &arr[i].h, &arr[i].w);
		arr[i].h = (h - arr[i].h)/u + 1;
		if(arr[i].h <= 0) {
			i--;
			n--;
		}
	}

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

	struct heap hp;	hp.len = 0;
	unsigned long remh = arr[0].h;
	unsigned long c, res = 0;
	inserth(&hp, &arr[0]);

	for(i=1;i<n;i++) {
		if(arr[i].h < arr[i-1].h)
			for(;remh > arr[i].h; remh--)
				if(!emptyh(hp))
					res += emaxh(&hp);
		inserth(&hp, &arr[i]);
	}
	for(;remh > 0 && !emptyh(hp); remh--)
		res += emaxh(&hp);

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

	free(arr);
	return 0;
}