Pagini recente » Cod sursa (job #1329794) | Cod sursa (job #1986341) | Cod sursa (job #253815) | Cod sursa (job #2535333) | Cod sursa (job #427343)
Cod sursa(job #427343)
#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("%lu %lu", &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;
}*/
unsigned long delta[100001];
unsigned long dinw[100001], cmax;
int j, jm;
char f;
/*for(i=0;i<n;i++)
fprintf(stderr,"%%%lu %lu\n",arr[i].h,arr[i].w);
*/
delta[0] = u;
dinw[0] = arr[0].w;
for(i=1;i<n;i++) {
f = 0;
cmax = 0;
for(j=0;j<i;j++) {
//fprintf(stderr,"-%lu %lu \n",delta[j],arr[i].h);
if((delta[j] + arr[i].h) <= h && dinw[j] > cmax) {
cmax = dinw[j];
jm = j;
if(!f) f = 1;
}}
if(!f) {
delta[i] = u;
dinw[i] = arr[i].w;
} else {
delta[i] = delta[jm] + u;
dinw[i] = arr[i].w + cmax;
}
//fprintf(stderr,"%lu %lu\n", delta[i], dinw[i]);
}
res = 0;
for(i=0;i<n;i++)
if(dinw[i] > res)
res = dinw[i];
printf("%ld\n", res);
free(arr);
return 0;
}