Cod sursa(job #439764)

Utilizator dragosiordachedragos iordache dragosiordache Data 11 aprilie 2010 19:09:49
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.13 kb
#include "stdio.h"

typedef struct {
	int h,g;
} gutui;

int cmp(void* a, void* b)
{
	return ((gutui*)b)->h - ((gutui*)a)->h;
}

int insertArb(int g, int* arb, int n)
{
	while ((n-1)/2>=0 && n!=0 && g<arb[(n-1)/2])
	{
		arb[n] = arb[(n-1)/2];
		n = (n-1)/2;
	}
	arb[n] = g;
	return n;
}

int inlocuiesteMin(int g, int *arb, int n)
{
	int i=0;
	while ((2*i+1<n && g>arb[2*i+1]) || (2*i+2<n && g>arb[2*i+2]))
		if ((2*i+2<n && arb[2*i+1]<=arb[2*i+2]) || 2*i+2==n)
		{	
			arb[i] = arb[2*i+1];
			i = 2*i+1;
		}
		else if (2*i+2<n && arb[2*i+1]>arb[2*i+2])
		{
			arb[i] = arb[2*i+2];
			i = 2*i+2;
		}
	arb[i] = g;
	return i;
}

int main() 
{
	FILE *f, *g;
	f = fopen("gutui.in", "r");
	g = fopen("gutui.out", "w");
	int n,i;
	int h,u;

	fscanf(f, "%i %i %i", &n,&h,&u);
	gutui a[n];
	int arb[n];
	
	for (i=0;i<n;i++)
		fscanf(f, "%i %i", &a[i].h, &a[i].g);

	qsort(a, n, sizeof(gutui), cmp);
	
	int nr = 0;
	for (i=0;i<n;i++)
		if (a[i].h<=h-nr*u) 
			insertArb(a[i].g, arb, nr++);
		else if (a[i].g>arb[0])
			inlocuiesteMin(a[i].g, arb, nr);

	int tot=0;
	for (i=0;i<nr;i++)
		 tot+=arb[i];
	
	fprintf(g, "%u", tot);

	fclose(f);
	fclose(g);
	
	return 0;
}