Cod sursa(job #463072)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 14:58:27
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.82 kb
#include <stdio.h>
#include <memory.h>
#include <malloc.h>

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

//max heap on unsigned longs
typedef unsigned long ElementType;

#define MaxData ((ElementType)0xFFFFFFFF)

typedef struct HeapStruct {
    int Capacity;
    int Size;
    ElementType *Elements;
} *MaxHeap;

MaxHeap Initialize(int MaxElements);
void Destroy(MaxHeap H);
void MakeEmpty(MaxHeap H);
void Insert(ElementType X, MaxHeap H);
ElementType DeleteMax(MaxHeap H);
ElementType FindMax(MaxHeap H);
int IsEmpty(MaxHeap H);
int IsFull(MaxHeap H);

MaxHeap Initialize(int MaxElements) {
    MaxHeap H;

    H = (MaxHeap)malloc(sizeof(struct HeapStruct));
    if (H == NULL)
    	fprintf(stderr,"Out of space!!!");

    /* Allocate the array plus one extra for sentinel */
    H->Elements = malloc((MaxElements + 1) * sizeof ( ElementType));
    if (H->Elements == NULL)
    	fprintf(stderr, "Out of space!!!");

    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[ 0 ] = MaxData;

    return H;
}

void MakeEmpty(MaxHeap H) {
    H->Size = 0;
}

/* H->Element[ 0 ] is a sentinel */

void Insert(ElementType X, MaxHeap H) {
    int i;

    if (IsFull(H)) {
        fprintf(stderr, "Priority queue is full");
        return;
    }

    for (i = ++H->Size; H->Elements[ i / 2 ] < X; i /= 2)
        H->Elements[ i ] = H->Elements[ i / 2 ];
    H->Elements[ i ] = X;

}

/* END */


ElementType DeleteMax(MaxHeap H) {
    int i, Child;
    ElementType MaxElement, LastElement;

    if (IsEmpty(H)) {
    	fprintf(stderr, "Priority queue is empty");
      return H->Elements[ 0 ];
    }
    MaxElement = H->Elements[ 1 ];
    LastElement = H->Elements[ H->Size-- ];

    for (i = 1; i * 2 <= H->Size; i = Child) {
    /* Find smaller child */
    	Child = i * 2;
      if (Child != H->Size && H->Elements[ Child + 1 ] > H->Elements[ Child ])
      	Child++;

      /* Percolate one level */
      if (LastElement < H->Elements[ Child ])
      	H->Elements[ i ] = H->Elements[ Child ];
      else
      	break;
    }
    H->Elements[ i ] = LastElement;
    return MaxElement;
}

ElementType FindMax(MaxHeap H) {
    if (!IsEmpty(H))
        return H->Elements[ 1 ];
    fprintf(stderr, "Priority Queue is Empty");
    return H->Elements[ 0 ];
}

int IsEmpty(MaxHeap H) {
    return H->Size == 0;
}

int IsFull(MaxHeap H) {
    return H->Size == H->Capacity;
}

void Destroy(MaxHeap H) {
    free(H->Elements);
    free(H);
}

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

  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;
	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 || arr[i].w == 0) {
			i--;
			n--;
		}
	}

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

	MaxHeap hp = Initialize(n);
	unsigned long remh = arr[0].h;
	unsigned long res = 0;
	Insert(arr[0].w, hp);

	for(i=1;i<n;i++) {
		if(arr[i].h < arr[i-1].h)
			for(;remh > arr[i].h; remh--)
				if(!IsEmpty(hp)) {
					res += FindMax(hp);
					DeleteMax(hp);
				}
		Insert(arr[i].w, hp);
	}
	for(;remh > 0 && !IsEmpty(hp); remh--) {
		res += FindMax(hp);
		DeleteMax(hp);
	}

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

	Destroy(hp);
	free(arr);
	return 0;
}