Cod sursa(job #427343)

Utilizator adyk18enache adrian adyk18 Data 27 martie 2010 19:19:18
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.18 kb
#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;
}