Cod sursa(job #435650)

Utilizator bogdan.davidoaiaDavidoaia Bogdan bogdan.davidoaia Data 7 aprilie 2010 18:46:26
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.46 kb
// Davidoaia Bogdam-Mihai	323CA

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct gutuie { 
	long h;		// inaltimea gutuii
	long w; 	// greutatea gutuii
};


int comph(const void *e1, const void *e2) {
	struct gutuie *a = (struct gutuie *)e1;
	struct gutuie *b = (struct gutuie *)e2;
	
	if(a->h != b->h)
		return a->h - b->h;
	return b->w - a->w;
}

int compw(const void *e1, const void *e2) {
	struct gutuie *a = (struct gutuie *)e1;
	struct gutuie *b = (struct gutuie *)e2;
	
	if(a->w != b->w)
		return b->w - a->w;
	return a->h - b->h;
}

int main() {
	FILE *in = fopen("gutui.in", "r");
	FILE *out = fopen("gutui.out", "w");
	
	long n, u ,h;
	long i;
	struct gutuie *g;
	
	fscanf(in, "%ld%ld%ld", &n, &h, &u);
	g = (struct gutuie *) malloc(n * sizeof(struct gutuie));
	for( i = 0; i < n; i++) 
		fscanf(in, "%ld%ld", &(g[i].h), &(g[i].w) );
	
	
	// calculare inaltime minima a gutuilor
	long hmin = g[0].h;
	for(i = 1; i < n; i++)
			if(hmin > g[i].h)
				hmin = g[i].h;
	
	// calculare numar de nivele
	long nlevel = ceil( (h - hmin) / u ) + 1;			
	
	for( i = 0; i < n; i++)
		g[i].h = ceil( (h - g[i].h) / u);

	qsort(g, n, sizeof(struct gutuie), compw);
	
	long s = 0, *gathered = (long *) calloc(sizeof(long), n), ng = 0;
	for(i = 0; i < n; i++) {
		if( (g[i].h - gathered[g[i].h]) >= 0) {
			s += g[i].w;
			gathered[g[i].h]++;
			ng++;
			if(ng == nlevel)
				break;
		}
	}
	
	fprintf(out, "%ld\n", s);
	free(g);
	free(gathered);
	fclose(in);
	fclose(out);
	return 0;
}