Cod sursa(job #434490)

Utilizator dragosiordachedragos iordache dragosiordache Data 6 aprilie 2010 00:06:59
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.14 kb
#include "stdio.h"
int h,u;


typedef struct {
	int h,g;
} 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)
{
	return ((((gutui*)b)->g - ((gutui*)a)->g));
}

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[(h/u)*(h/u+1)/2];

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

	qsort(a, n, sizeof(gutui), cmp);
	/*for (i=0;i<n;i++)
		printf("%i %i\n", a[i].h, a[i].g);*/

	int m=0,   //pozitia in b
		 j=0,   //numarul de gutui din grupul curent
		 k=1;   //numarul grupului curent
	i=0; 
	while(i<n)
	{
		if (a[i].h > h-k*u)
		{
			if (j<k)
			{
				//printf("a");
				b[m++]=a[i];
				i++;
				j++;
			}
			else
			{
				//printf("c");
				i++;
			}
		}
		else
		{
			//printf("b");
			j=0;
			k++;
		}
	}
	/*printf("\n");
	for (i=0;i<m;i++)
		printf("%i %i\n", b[i].h, b[i].g);*/
	qsort(b, m, sizeof(gutui), cmp2);

	int tot=0;
	for (j=0;j<((h/u<m)?h/u:m);j++)
		tot+=b[j].g;
	fprintf(g, "%i", tot);

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