Cod sursa(job #434983)

Utilizator copotalex copot Data 6 aprilie 2010 19:43:01
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.65 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	unsigned int h;
	unsigned int g;
} gutuie;

gutuie vg[100000];
int N, H, U;

void citeste()
{
	FILE *f = fopen("gutui.in", "rt");
	int i;
	if ( f == NULL )
		return;
		
	fscanf(f, "%d%d%d", &N, &H, &U);
	for (i = 0; i < N; i++)
		fscanf(f, "%d%d", &vg[i].h, &vg[i].g);
	fclose(f);
}

int comp1(const void *s1, const void *s2)
{
	return ((gutuie*)s2)->h - ((gutuie*)s1)->h;
	//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}

int comp2(const void *s1, const void *s2)
{
	//return ((gutuie*)s2)->h - ((gutuie*)s1)->h;
	return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}

int comp3(const void *s1, const void *s2)
{
	return ((gutuie*)s2)->g - ((gutuie*)s1)->g;
	//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}

int main(int argc, char **argv)
{
	unsigned int maxg, sg, sol;
	unsigned int i, ncmax, nci;
	
	citeste();
	sg = 0;

	qsort(vg, N, sizeof(gutuie), comp3); 
	
	i = 0;
	ncmax = 0; // cate gutui voi culege
	while (i < N) {
	  if ( (H - vg[i].h) / U + 1 > ncmax )
	    ncmax = (H - vg[i].h) / U + 1;
	  i++;
	}
	
	sol = 0;
	for ( nci = 1; nci <= ncmax; nci++ ) {
		maxg = vg[i].g;
		sg = 0;
		i = 0;
		//nci =1
		while ( i < N && nci <= ncmax ) {
				if ((H - vg[i].h) / U + 1 == nci && vg[i].g > maxg) {
					maxg = vg[i].g;
				} else {
					sg = sg + maxg;
					maxg = vg[i].g;
					nci++;
				}
			i++;
		}
		sg = sg + maxg;
		if ( sg > sol)
			sol = sg;
	}

	printf("%d\n", sol);
	FILE *f = fopen("gutui.out", "wt");
	fprintf(f, "%d\n", sol);
	fclose(f);
	
	return 0;
}