Cod sursa(job #440427)

Utilizator CreationDinescu Stefan Creation Data 12 aprilie 2010 00:59:04
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 2.61 kb
#include <stdio.h>
#include <stdlib.h>

/*typedef struct{
	int inaltime;
	int greutate;
	int index;
}gutui;*/

///functie comparare pentru qsort
/*int compare (const void *a, const void *b){
	gutui *item1 = (gutui*)a;
	gutui *item2 = (gutui*)b;
	
	return -(item1->greutate - item2->greutate);
}

int compare1 (const void *a, const void *b){
	gutui *item1 = (gutui*)a;
	gutui *item2 = (gutui*)b;
	
	return (item1->inaltime - item2->inaltime);
}*/

int compare(const void *a,const void *b){
	return -(*(int*)a - *(int*)b);
}

int main(){
	FILE *fin=fopen("gutui.in","r");
	FILE *fout=fopen("gutui.out","w");
	
	int n,h,u;
	int i,j,k,inaltime,greutate;
	int total=0;
	int prim,secund,nr,nivel_prim,nivel_secund;
	
	fscanf(fin,"%d %d %d",&n,&h,&u);
	
	int **mat;
	
	mat=(int**)malloc((h/u+2)*sizeof(int*));
	for (i=0;i<=h/u+1;i++)
		mat[i]=(int*)malloc((n/2)*sizeof(int));
	
	
	//gutui *v=(gutui*)malloc(n*sizeof(gutui));
	int *v=(int*)malloc((h/u+2)*sizeof(int));
	int *aux=(int*)malloc((h/u+3)*sizeof(int));
	int *nivel=(int*)malloc((h/u+3)*sizeof(int));
	
	for (i=0;i<h/u+2;i++)
		nivel[i]=i;
	
	for (i=0;i<n;i++){
		fscanf(fin,"%d %d",&inaltime,&greutate);
		mat[(h-inaltime)/u+1][aux[(h-inaltime)/u+1]+1]=greutate;
		aux[(h-inaltime)/u+1]++;
	}
	
	
	nr=0;
	for (i=1;i<=h/u+1;i++){
		qsort(mat[i],n/2,sizeof(int),compare);
		if (aux[i]>0)
			nr++;
	}
		
		
	/*for (i=1;i<=h/u+1;i++){
		for (j=0;j<n/2;j++)
			printf("%d ",mat[i][j]);
		printf("\n");
	}
	
	printf("\n\n");
	for (i=0;i<=h/u+1;i++)
		printf("%d ",aux[i]);
	printf("\n");
	
	for (i=0;i<=h/u+1;i++)
		printf("%d ",v[i]);
	printf("\n\n");*/
	
	prim=mat[1][v[1]];
	nivel_prim=1;
	for (i=2;i<=h/u+1;i++)
		if (mat[i][v[i]]>=prim){
			secund=prim;
			nivel_secund=nivel_prim;
			prim=mat[i][v[i]];
			nivel_prim=i;
		}
		
		
	while (nr>0){
		
		total+=mat[nivel_prim][v[nivel_prim]];
		//printf("greutate = %d nr=%d nivel_prim=%d nivel=%d\n",mat[nivel_prim][v[nivel_prim]],nr,nivel_prim,nivel[nivel_prim]);
		k=nivel[nivel_prim];
		for (i=1;i<=h/u+1;i++)
			if (nivel[i]>=k)
				nivel[i]--;
		v[nivel_prim]++;
		/*if (v[nivel_prim]==nivel[nivel_prim])
			nr--;*/
			
		for (i=1;i<=h/u+1;i++)
			if ((v[i]==aux[i] && aux[i]>0)||(nivel[i]==0 && aux[i]>0)){
				nr--;
				aux[i]=0;
			}
			
		/*printf("nivele: ");
		for (i=1;i<=h/u+1;i++)
			printf("%d ",nivel[i]);
		printf("\n");
		
		printf("aux: ");
		for (i=1;i<=h/u+1;i++)
			printf("%d ",aux[i]);
		printf("\n");*/
		
		prim=-1;
		for (i=1;i<=h/u+1;i++)
			if (aux[i]>0 && prim<mat[i][v[i]]){
				prim=mat[i][v[i]];
				nivel_prim=i;
			}
	}
	
	
	fprintf(fout,"%d",total);///solutia finala
	fclose(fin);
	fclose(fout);
	//free(v);
	//free(nivel);
	return 0;
}