Cod sursa(job #438644)

Utilizator ana.ionana ion ana.ion Data 10 aprilie 2010 22:19:02
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 1.08 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct fruct{
	int ht;
	int wt;
	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];
	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[maxim+1];
	for ( i=1; i<maxim+1; i++)
		level[i]=-10;
	for ( i=0; i<n; i++)
		if (vec[i].ht<h){
			if ( level[vec[i].niv]==-10 ){
				level[vec[i].niv]=i;
				prada=prada+vec[i].wt;
				}
			else{
				for ( j=vec[i].niv-1; j>0; j--)
					if ( level[j]==-10){
						level[j]=i;
						prada=prada+vec[i].wt;
						break;
						}
				}
			}
	fprintf(fout,"%d",prada);
	fclose(fin);
	fclose(fout);
	return 0;
}