Cod sursa(job #438780)

Utilizator gainushaTatulescu Stefan gainusha Data 11 aprilie 2010 00:25:23
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.22 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct gutuie {
	int wgt;
	int hgt;
} gutuie;

int comp( const void *e1, const void *e2 ) {
	gutuie *a = (gutuie*)(e1);
	gutuie *b = (gutuie*)(e2);
	if ( (*a).wgt == (*b).wgt )
		return (*b).hgt - (*a).hgt;
	return (*a).wgt - (*b).wgt;
}

int main() {
	gutuie v[100000];
	int aran[100000];
	FILE *f = fopen( "gutui.in" , "r" );
	FILE *g = fopen( "gutui.out", "w" );
	int N, H, U, i, Wmax, X, j, Xmax;
	
	fscanf ( f, "%d %d %d", &N, &H, &U );
	for ( i=0; i<N; i++ ) {
		fscanf( f, "%d %d", &v[i].hgt, &v[i].wgt);
		aran[i] = -1;
	}
	Xmax = 0;
	Wmax = 0;
	
	qsort( v, N, sizeof(gutuie), comp );
	
	/*for ( i=0; i<N; i++) {
		printf("%d %d\n", v[i].hgt, v[i].wgt);
	}*/
	
	for ( i=N-1; i>=0; i-- ) {
		X = (H - v[i].hgt) / U;
		j = X+1;
		if ( X<0) continue;
		if ( X+1>Xmax ) Xmax = X+1;
		while ( j>0 && aran[j]!=-1 ) j--;
		if ( j>0 ) aran[j] = i;
			
		/*if ( v[i].hgt + dH <= H ) {
			Wmax += v[i].wgt;
			dH += U;
			if ( H < dH )
				break;
		}*/
	}
	
	for ( i=1; i<=Xmax; i++ ) {
		if ( aran[i] != -1 ) Wmax += v[ aran[i] ].wgt;
	}
	/*for ( i=1; i<=Xmax; i++) {
		printf("%d %d\n", v[ aran[i] ].hgt, v[ aran[i] ].wgt);
	}*/
	
	fprintf( g, "%d\n", Wmax );
	
	fclose(f);
	fclose(g);
	return 0;
}