Cod sursa(job #440541)

Utilizator sshdas21Ionut Moise sshdas21 Data 12 aprilie 2010 07:58:37
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.4 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int main()
{
	int i, j, idx, N, other_N, H, U, max, *h, *w, *marked, *picked, solution;

	freopen(file_in, "rt", stdin);
	freopen(file_out, "wt", stdout);

	scanf("%i %i %i", &N, &H, &U);
	h = (int *)malloc(N*sizeof(int));
	w = (int *)malloc(N*sizeof(int));
	for(i = 0; i < N; i++) 
		scanf("%i %i", h+i, w+i);

	marked = (int *)malloc(N*sizeof(int));
	picked = (int *)malloc(N*sizeof(int));

	j = 0;
	solution = 0;
	other_N = N;
	memset(picked, 0, N*sizeof(int));

	while(j < N)
	{
		memset(marked, 0, N * sizeof(int));

		for(i=0;i<N;i++)
		{
			if(h[i]+U*(j+1) > H)
				marked[i] = 1;
			if(h[i]+U*j > H)
				picked[i] = 1;
		}

		max = 0;
		idx = 0;

		for(i=0;i<N;i++)
		{
			if((marked[i] == 1) && (picked[i] == 0) && (w[i] > max))
			{
				max = w[i];
				idx = i;
			}
		}

		if(max == 0)
		{
			for(i=0;i<N;i++)
				if((marked[i] == 0) && (picked[i] == 0) && (w[i] > max))
				{
					max = w[i];
					idx = i;
				}
		}

		/*for(i=0;i<N;i++)
			printf("%i ", marked[i]);
		for(i=0;i<N;i++)
			printf("%i~", picked[i]);

		printf("\n");*/

		picked[idx] = 1;
		solution += max;
		//printf("%i\n", max);
		j++;
	}

	printf("%i", solution);

	free(h);
	free(w);
	free(marked);
	fclose(stdin);
	fclose(stdout);

	return 0;
}