Pagini recente » Cod sursa (job #1569617) | Cod sursa (job #817780) | Cod sursa (job #2672917) | Cod sursa (job #1623058) | Cod sursa (job #426475)
Cod sursa(job #426475)
#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;
}