Cod sursa(job #438710)

Utilizator ana.ionana ion ana.ion Data 10 aprilie 2010 23:14:44
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.38 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));
	int nr=0;
	for (i = 0; i < n; ++i)
        {
        scanf("%d %d",&vec[i].ht,&vec[i].wt);
        vec[i].niv=(h-vec[i].ht)/u+1;
        if (nr < vec[i].niv)
           nr = vec[i].niv;
        if( vec[i].ht > h )
            {
            i--;
            n--;
            }
        }
	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((nr+1)*sizeof(int));
	for ( i=1; i<nr+1; i++)
		level[i]=-1;
	for ( i=0; i<nr; 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>0; j--)
					if ( level[j]==-1){
						level[j]=i;
						prada=prada+vec[i].wt;
						break;
						}
				if ( j==0 && nr<=n)
					nr++;
				}
			}
	fprintf(fout,"%d",prada);
	fclose(fin);
	fclose(fout);
	return 0;
}