Cod sursa(job #440220)

Utilizator rurryRuxandra Nistor rurry Data 11 aprilie 2010 22:55:39
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.1 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct {
	int height;
	int weight;
} fruit;

int compare (const void * a, const void * b)
{
	return (((fruit *)b ) ->weight - ((fruit *)a ) ->weight);
}


int main(){
	unsigned int h, u,  hmin;
	int n, i;
	fruit *x;
	
	//se citesc datele din fisier
	FILE *fin = fopen("gutui.in", "r");
	fscanf(fin, "%d", &n);
	fscanf(fin,"%d", &h);
	fscanf(fin, "%d", &u);
	
	x = (fruit *) malloc( n *sizeof(fruit));
	hmin = h;
	for(i = 0; i < n; i++){
		fscanf(fin, "%d %d", &(x[i].height), &(x[i].weight));
		if(x[i].height < hmin)
			hmin = x[i].height;
	}
	fclose(fin);
	qsort(x, n, sizeof(x), compare);

	int greutate = 0;
	int *cules;
	int moment;
	cules = (int * ) calloc ((( h - hmin) / u + 2), sizeof (int));
	for (i = 0; i < n; i++){
		if(h > x[i].height){
			moment = (h - x[i].height) / u;

			while(moment >= 0 && cules[moment]){
				moment --;
			}

			if(moment >= 0){
				cules[moment] = 1;
				greutate += x[i].weight;
			}
		}
	}
	FILE *fout = fopen("gutui.out", "w");
	fprintf(fout, "%d\n", greutate);
	fclose(fout);	
	//printf("greutate : >%u<", greutate);	
	return 0;
}