Cod sursa(job #436334)

Utilizator ana.ionana ion ana.ion Data 8 aprilie 2010 15:02:05
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.1 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct fruct{
	unsigned int ht;
	unsigned int wt;
} fruct;
int compare ( const void * a, const void * b){
	fruct f1, f2;
	f1 = *(fruct*)a;
	f2 = *(fruct*)b;
	return (f2.ht-f1.ht);
}
int main (){
	FILE * fin = fopen ( "gutui.in", "r");
	FILE * fout = fopen ( "gutui.out", "w");
	long n, h, u;
	int i;
	fruct vec[100000];
	fscanf( fin, "%ld", &n);
	fscanf( fin, "%ld", &h);
	fscanf( fin, "%ld", &u);
	for ( i=0; i<n; i++ ){
		fscanf (fin, "%d%d", &vec[i].ht, &vec[i].wt);
	}
	qsort(vec, n, sizeof(fruct), compare);
	i=0;
	int prada = 0, found;
	int gata =0, j, aux;
	while ( (h>=0) && (gata==0) ){
		found=0;
		while ( (found==0) && (i<n) ){
			if ( vec[i].ht<=h ){
				//printf("h aici %ld si pozitia %d\n",h,i);
				j=i;
				while ( vec[i].ht==vec[j].ht ){
					if ( vec[j].wt>vec[i].wt ){
						aux=vec[i].wt;
						vec[i].wt=vec[j].wt;
						vec[j].wt=aux;	
					}
					j++;
				}
				found=1;
			}
			i++;
		}
		if ( found==1 ){
			prada = prada + vec[i-1].wt;
			h = h-u;
		}
		else
			gata=1;
	}
	fprintf (fout,"%d\n", prada);
	fclose ( fin );
	fclose ( fout );
	return 0;
}