Cod sursa(job #441790)

Utilizator emilia.ciobanuCiobanu Emilia Maria Silvia emilia.ciobanu Data 13 aprilie 2010 13:13:22
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.57 kb
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

#define MINF INT_MIN
#define PINF INT_MAX
#define IN "gutui.in"
#define OUT "gutui.out"
#define Left(i) ((i)<<1)
#define Right(i) (((i)<<1) + 1)
#define Father(i) ((i)>>1)

typedef struct
{
	int h;
	int w;
} GUTUIE;

typedef struct
{
	int head;	//unde adaug urmatorul element in heap
	int dim;
	GUTUIE *values;
} HEAP, *PHEAP;

PHEAP CreateV (int dim)
{
	int i;

	PHEAP H = (PHEAP) calloc (1, sizeof(HEAP));
	H->dim = dim;
	H->head = 1;
	H->values = (GUTUIE*)calloc(dim+1, sizeof(GUTUIE));

	for (i = 1 ; i <= H->dim ; ++i)
	{
		H->values[i].h = MINF;
		H->values[i].w = PINF;
	}

	return H;
}

void FreeV (PHEAP H)
{
	free (H->values);
	free (H);
}

void print_g(GUTUIE G)
{
	printf("Gutuie :\tinaltime: %d\t greutate: %d\n", G.h, G.w);
	printf("\n");
}

void Print (PHEAP H)
{
	int i;
	for (i = 1 ; i <= H->dim ; ++i)
		print_g (H->values[i]);
	printf("\n");
}

void RHeap (PHEAP H, int poz)
{
	int left = Left(poz);
	int right = Right(poz);
	int minim = PINF;

	if (left <= H->head-1 && ((H->values[left]).w < (H->values[poz]).w) )
		minim = left;
	else
		minim = poz;
	if (right <= H->head-1 && ((H->values[right]).w < (H->values[minim]).w) )
		minim = right;

	if (minim != poz)
	{
		GUTUIE *aux = (GUTUIE*)calloc (1, sizeof(GUTUIE));
		*aux = H->values[poz];
		H->values[poz] = H->values[minim];
		H->values[minim] = *aux;

		free(aux);

		RHeap (H, minim);
	}

}

void CreateH (PHEAP H)
{
	int i;
	for (i = H->dim/2 ; i >= 1; --i)
	{
		RHeap (H, i);
		H->head++;
	}
}

void ShiftUp (PHEAP H, int poz)
{
	int father = Father (poz);
	if (H->values[father].w > H->values[poz].w)
	{
		GUTUIE aux = H->values[poz];
		H->values[poz] = H->values[father];
		H->values[father] = aux;
		if (father == 0)
			return;
		ShiftUp(H, father);
	}
	else
		return;
}

int Add (PHEAP H, GUTUIE g)
{
	if (H->head > H->dim+1)
		return -1;

	H->values[H->head] = g;
	ShiftUp (H, H->head);
	H->head++;
	return 1;
}

GUTUIE ExtractMin (PHEAP H)
{
	GUTUIE aux = H->values[1];
	H->values[1] = H->values[H->head-1];
	H->head--;
	RHeap (H, 1);
	return aux;
}

int compare (const void *a, const void *b)
{
	return ((GUTUIE*)b)->h - ((GUTUIE*)a)->h;
}

unsigned long GetWeight (PHEAP H)
{
	unsigned long G = 0;
	GUTUIE *g = (GUTUIE*) calloc (1, sizeof(GUTUIE));

	while (1)
	{
		*g = ExtractMin (H);
	//	printf("%d\t", g->w);
		G += g->w;
		if (H->head == 1)
			break;
	}
	free(g);

	return G;
}

int main (int argc, char **argv)
{
	int N, H, U, i, j;
	unsigned long G = 0;
	GUTUIE *g;

	FILE *fin  = fopen (argv[1], "r");
	FILE *fout = fopen (OUT, "w");

	fscanf (fin, "%d%d%d", &N, &H, &U);

	g = (GUTUIE*) calloc (N, sizeof(GUTUIE));
	PHEAP Heap = CreateV (N+1);

	for (i = 0; i < N; ++i)
		fscanf(fin, "%d%d", &g[i].h, &g[i].w);

	qsort (g, N, sizeof(GUTUIE), compare);

	int cnt;
	int prev = H/U+1, current = 0;
	GUTUIE *aux = (GUTUIE*) calloc (1, sizeof(GUTUIE));

	for (i = 0; i < N; ++i)
	{
		current = g[i].h/U + 1;
		cnt = prev - current;

		if (cnt > 1)
		{
			for (j = 0 ; j < cnt ; ++j)
			{
				if ( i+j >= N )
					break;
				Add (Heap, g[i+j]);
				G += g[i+j].w;
			}
			i = i + cnt - 1;
			prev = current;
			continue;
		}

		if (current == prev)
		{
			if (g[i].h + i * U <= H)
			{
				Add (Heap, g[i]);
				G += g[i].w;
			}
			else if (g[i].w > Heap->values[1].w)
			{
				*aux = ExtractMin (Heap);
				Add (Heap, g[i]);
				G += (g[i].w - aux->w);
			}

		}
	
		else
		{
			Add (Heap, g[i]);
			G += g[i].w;
		}

		prev = current;

	}

	free (aux);

	G = GetWeight (Heap);


	fprintf (fout, "%lu\n", G);
	//printf ("%ld\n", G);

	fclose(fin);
	fclose(fout);
	FreeV (Heap);
	free (g);

	return 0;
}