Cod sursa(job #437629)

Utilizator dragosiordachedragos iordache dragosiordache Data 9 aprilie 2010 23:26:32
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.2 kb
#include "stdio.h"
int h,u;


typedef struct {
	int h,g;
	int val;
} gutui;

int cmp(void* a, void* b)
{
	int x = (((gutui*)b)->h)/u - (((gutui*)a)->h)/u;
	return (x?x:(((gutui*)b)->g - ((gutui*)a)->g));
}

int cmp2(void* a, void* b)
{
	int x = ((gutui*)b)->g - ((gutui*)a)->g;
	//return (x?x:((gutui*)b)->val - ((gutui*)a)->val);
	return x;
}

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

	fscanf(f, "%i %i %i", &n,&h,&u);
	gutui a[n];
	gutui b[n];

	for (i=0;i<n;i++)
	{
		fscanf(f, "%i %i", &a[i].h, &a[i].g);
		a[i].val = 0;
	}

	qsort(a, n, sizeof(gutui), cmp2);
	
	int c[h/u+1];
	for (i=0;i<=h/u;i++)
		c[i]=0;
	unsigned int tot=0;
	int contor = 0,j,k;
	int boo = 0;
	int indice;
	for (j=0;j<n && contor<h/u+1;j++)
	{
		indice = (h-a[j].h)/u;
		c[indice]++;//vad daca gutuia curenta poate intra la solutie
		for (i=0,boo=1,k=-1;i<h/u+1 && boo;i++)
		{
			k+=c[i];
			if (k>i) boo = 0;//verific daca dupa ce o adaug la solutie poate fi culeasa
		}
		if (boo)
		{
			tot+=a[j].g;
			printf("%i %i\n", a[j].h, a[j].g);				
			contor++;
		}
		else
		{
			c[indice]--;//daca nu
		}
	}
	fprintf(g, "%u", tot);

	printf("%u\n", tot);

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