Cod sursa(job #430147)

Utilizator copotalex copot Data 30 martie 2010 19:53:53
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int h;
	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)
{
	int maxg, sg, sg2;
	int i, su, 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++;
	}
	
	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;

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