Cod sursa(job #437793)

Utilizator catalin.cioponeaCatalin Cioponea catalin.cioponea Data 10 aprilie 2010 02:07:44
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>


typedef struct copac{
	int inaltime;
	int greutate;
}gutui;

int compare (const void * a, const void * b){
	gutui *x, *y;
	x = (gutui*)a;
	y = (gutui*)b;
	return y->greutate - x->greutate;
}

int main(){
	FILE *f = fopen("gutui.in", "r");
	FILE *g = fopen("gutui.out", "w");
	
	int N; // N = numarul de gutui din pom
	fscanf(f, "%d", &N);
	int H; // H = inaltimea maxima la care poate ajunge Gigel
	fscanf(f, "%d", &H);
	int U; // U = cu cat se ridica crengile copacului
	fscanf(f, "%d", &U);
	
	int *inaltimi, *greutati;
	gutui *pom;
	pom = (gutui *) malloc ( N * sizeof(gutui));
	int i, j;
	for (i = 0; i < N; i++){
		fscanf(f, "%d", &pom[i].inaltime);
		fscanf(f, "%d", &pom[i].greutate);
	}
	qsort(pom, N, sizeof(gutui), compare); //aici fac sortarea descrescatoare dupa greutate
	
	//calculez momentul pentru fiecare gutuie
	int *moment = (int *) malloc ( N * sizeof(int));
	for ( i = 0; i < N; i++ ){
		moment[i] = ( H - pom[i].inaltime) / U ;
	}

	int valabil[N];
	for ( i = 0; i < N; i++ ){
		valabil[i] = 0;//initial toate momentele sunt accesabile
	}

	int greutateaCuleasa = 0;
	for ( i = 0; i < N; i++ ){
		if ( valabil[moment[i]] == 0 ){
			valabil[moment[i]] = 1;
			greutateaCuleasa += pom[i].greutate;
		}
		else{
			for ( j = moment[i]; j >= 0; j-- ){
				if ( valabil[j] == 0 ){
					valabil[j] = 1;
					greutateaCuleasa += pom[i].greutate;
					break;
				}
			}
		}
	}
	
	fprintf(g, "%d", greutateaCuleasa);
	fclose(f);
	fclose(g);

	return 0;
}