Pagini recente » Cod sursa (job #3278988) | Cod sursa (job #255286) | Cod sursa (job #255303) | Cod sursa (job #429371) | Cod sursa (job #428006)
Cod sursa(job #428006)
#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) {
if(h->len==0){
h->v[0] = x;
} else {
int i;
for(i=h->len-1;i>=1;i--) {
if(h->v[i]->w <= x->w)
break;
else {
h->v[i+1] = h->v[i];
}
}
if(i==0) {
h->v[1] = h->v[0];
h->v[0] = x;
}else
h->v[i+1] = x;
}
h->len ++;
return;
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) {
h->len --;
return h->v[h->len]->w;
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 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, 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;
}