Cod sursa(job #442283)

Utilizator sshdas21Ionut Moise sshdas21 Data 14 aprilie 2010 05:01:31
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.23 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define file_in "gutui.in"
#define file_out "gutui.out"

typedef struct fruit_
{
	long int height;
	long int weight;
} fruit;

fruit *fruits, *solution;
long int N, U, H, *used, max = 0;

void bkt(int ind, fruit *solution)
{	
	long int i, sum;

	if(solution[ind-1].height + U*ind > H)
	{
		sum = 0;
		for(i=0;i<ind;i++)
			sum += solution[i].weight;

		if(max < sum)
			max = sum;
	}
	else
	{
		for(i=0;i<N;i++)
		{
			if(!used[i])
			{
				solution[ind] = fruits[i];

				if(solution[ind].height + U*(ind-1) <= H)
				{
					used[i] = 1;
					bkt(ind+1, solution);
					used[i] = 0;
				}
			}
		}
	}
}

int main()
{
	long int i;
	freopen(file_in, "rt", stdin);
	freopen(file_out, "wt", stdout);

	scanf("%li %li %li", &N, &H, &U);
	fruits = (fruit *)malloc(N*sizeof(fruit));
	solution = (fruit *)malloc(N*sizeof(fruit));
	used = (long int *)malloc(N*sizeof(long int));
	memset(used, 0, N*sizeof(long int));

	for(i = 0; i < N; i++) 
		scanf("%li %li", &fruits[i].height, &fruits[i].weight);

	bkt(0,solution);

	printf("%li",max);

	free(fruits);
	free(solution);
	free(used);
	fclose(stdin);
	fclose(stdout);

	return 0;
}