Cod sursa(job #438683)

Utilizator ana.ionana ion ana.ion Data 10 aprilie 2010 22:49:58
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 1.16 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct fruct{
	unsigned int ht;
	unsigned int wt;
	unsigned int niv;
} fruct;
int compare ( const void * a, const void * b){
	fruct f1, f2;
	f1 = *(fruct*)a;
	f2 = *(fruct*)b;
	return f2.wt-f1.wt;
}
int main (){
	FILE * fin = fopen ( "gutui.in", "r");
	FILE * fout = fopen ( "gutui.out", "w");
	long n, u, h;
	int i;
	fscanf( fin, "%ld", &n);
	fscanf( fin, "%ld", &h);
	fscanf( fin, "%ld", &u);
	fruct* vec=(fruct*)malloc(n*sizeof(fruct));
	for ( i=0; i<n; i++ ){
		fscanf (fin, "%d%d", &vec[i].ht, &vec[i].wt);
		vec[i].niv=(h-vec[i].ht)/u+1;
	}
	int prada = 0;
	int j;
	qsort(vec, n, sizeof(fruct), compare);
	int maxim=vec[0].niv;
	for ( i=1; i<n; i++)
		if ( vec[i].niv>maxim )
			maxim=vec[i].niv;
	int *level=(int*)malloc((maxim+1)*sizeof(int));
	for ( i=1; i<maxim+1; i++)
		level[i]=-1;
	for ( i=0; i<n; i++)
		if (vec[i].ht<h){
			if ( level[vec[i].niv]==-1 ){
				level[vec[i].niv]=i;
				prada=prada+vec[i].wt;
				}
			else{
				for ( j=vec[i].niv-1; j>1; j--)
					if ( level[j]==-1){
						level[j]=i;
						prada=prada+vec[i].wt;
						break;
						}
				}
			}
	fprintf(fout,"%d",prada);
	fclose(fin);
	fclose(fout);
	return 0;
}