Cod sursa(job #429971)

Utilizator copotalex copot Data 30 martie 2010 17:37:10
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.57 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 main(int argc, char **argv)
{
	int maxi_curent;
	int maxg, sg, sg2;
	int i, su;
	
	citeste();
	qsort(vg, N, sizeof(gutuie), comp1); 
	
	i = 1;
	maxg = vg[0].g;
	sg = 0;
	maxi_curent = 0;
	su = U;
	while ( i < N ) {
		if ( vg[i].h + su <= H )
			if ( vg[maxi_curent].h - vg[i].h < U) {
				if ( vg[i].g > maxg )
					maxg = vg[i].g;
			} else90 {
				sg = sg + maxg;
				maxg = vg[i].g;
				su += U;
			}
		i++;
		
	}
	sg = sg + maxg;
	
	qsort(vg, N, sizeof(gutuie), comp2); 
	i = 1;
	maxg = vg[0].g;
	sg2 = 0;
	maxi_curent = 0;
	su = U;
	while ( i < N ) {
		if ( vg[i].h + su <= H )
			if ( vg[maxi_curent].h - vg[i].h < U) {
				if ( vg[i].g > maxg )
					maxg = vg[i].g;
			} else {
				sg2 = sg2 + maxg;
				maxg = vg[i].g;
				su += U;
			}
		i++;
		
	}
	sg2 = sg2 + maxg;
	if ( sg2 > sg )
		sg = sg2;
	FILE *f = fopen("gutui.out", "wt");
	fprintf(f, "%d\n", sg);
	fclose(f);
	
	return 0;
}