Cod sursa(job #437408)

Utilizator ana.ionana ion ana.ion Data 9 aprilie 2010 18:03:04
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.18 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[n+1];
	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;
	}
	long prada = 0;
	int j;
	qsort(vec, n, sizeof(fruct), compare);
	for (i=0; i<n; i++)
		printf("%d %d %d\n",vec[i].ht,vec[i].wt,vec[i].niv);
	int m;
	m = h/u;
	int level[m+1];
	for (i=1; i<m+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;
			else{
				for (j=vec[i].niv-1;j>=1;j--)
					if ( level[j]==-1 )
						break;
				if (j>=1)
					level[j]=i;
			}
		}
	}
	for (i=1; i<m+1; i++)
		if (level[i]!=-1){
			//printf("%d ", vec[level[i]].wt);
			prada = prada + vec[level[i]].wt;
		}
	fprintf (fout,"%ld\n", prada);
	fclose ( fin );
	fclose ( fout );
	return 0;
}