Pagini recente » Cod sursa (job #2806845) | Cod sursa (job #2960403) | Cod sursa (job #1124620) | Cod sursa (job #2239831) | Cod sursa (job #463072)
Cod sursa(job #463072)
#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;
}