Cod sursa(job #439298)

Utilizator TokPhobiaCosoi Andrei TokPhobia Data 11 aprilie 2010 15:10:14
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>

#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define INFINIT 4294967295
#define NMAX 100002
#define byte unsigned char

typedef struct gutuie {
	int g, h;
	gutuie *next;
} gutuie;

int min(int a, int b) {
	if (a<b) return a;
	return b;
}

int insert(byte viz[NMAX], gutuie *gutui, int h, int u, int n) {
	int nivel_dorit = min(n,(h-gutui->h)/u);
	
	while (viz[nivel_dorit]) {
		nivel_dorit--;
		if (nivel_dorit<0) return 0;
	}
	
	viz[nivel_dorit] = 1;

	return 1;
}

int comparator(const void * a, const void * b) {
	return -1*(((gutuie*)a)->g - ((gutuie*)b)->g);
}

int main() {
	
	FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
	int n, h, u, i;
	long int totalsum = 0;
	gutuie gutui[NMAX];
	byte viz[NMAX];
	
	//citim datele intr-o lista de gutui
	fscanf(fin, "%d %d %d", &n, &h, &u);
	
	for (i=0; i<n; i++) {
		fscanf(fin, "%d %d", &gutui[i].h, &gutui[i].g);
		viz[i] = 0;
	}
	viz[n] = 0;
	//sfarsit citit date
	
	//sortam datele
	qsort(gutui, n, sizeof(gutuie), comparator);
	
	//luam gutuile in ordinea descrescatoare a greutatii
	for (i=0; i<n; i++)
		//vedem daca putem pune gutuia maxima in lista
		if (insert(viz, &gutui[i], h, u, n))
			totalsum += gutui[i].g;
	
	fprintf(fout, "%ld\n", totalsum);
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}