Cod sursa(job #443068)

Utilizator jnkFDHSponge Bob jnkFDH Data 15 aprilie 2010 22:53:04
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 2.44 kb
#include<stdio.h>
#include<stdlib.h>
struct Fruct {
	int h;
	int w;
	int nivel;
};
typedef struct Fruct fruct;
fruct *copac;



int N,H,U,nrNivele;
int comparare2(const void *a,const void *b)
{
	if(*(int*)a > *(int*)b)
		return -1;
	if(*(int*)a < *(int*)b)
		return 1;
	return 0;
}
int comparare(const void *a, const void *b)
{
	const fruct *A = a;
	const fruct *B = b;
	if(A->h < B->h)
		return 1;
	if(A->h > B->h)
		return -1;
	if(A->w < B->w)
		return 1;
	if(A->w > B->w)
		return -1;
	return 0;
}
int comparare3(const void *a, const void *b)
{
	const fruct *A = a;
	const fruct *B = b;
	if(A->nivel > B->nivel)
		return 1;
	if(A->nivel < B->nivel)
		return -1;
	if(A->w < B->w)
		return 1;
	if(A->w > B->w)
		return -1;
	return 0;
}
void displayTree()
{
	int i;
	printf("\n%d\n",nrNivele);
	for(i=0;i<N;i++)
	{
		printf("%d %d %d\n",copac[i].h,copac[i].w,copac[i].nivel);
	}
}
int main()
{
	int i,j,l,k;
	int rezultat = 0;
	int *fructeAlese;
	int fa;
	FILE *fin,*fout;
	fin=fopen("gutui.in","r");
	fout=fopen("gutui.out","w");
	fscanf(fin,"%d%d%d",&N,&H,&U);
	copac=(struct Fruct*)malloc(N*sizeof(struct Fruct));
	for(i=0;i<N;i++)
	{
		fscanf(fin,"%d%d",&copac[i].h,&copac[i].w);
		copac[i].nivel=0;
	}
	
	qsort(copac,N,sizeof(struct Fruct),comparare);
	
	for(i=0;i<N;i++)
	{
		copac[i].nivel=(H-copac[i].h)/U;
	}
	
	qsort(copac,N,sizeof(struct Fruct),comparare3);
	nrNivele=copac[N-1].nivel + 1;
	fructeAlese=(int*)malloc(nrNivele*sizeof(int));
	//alegerea fructelor:
	
	/*i=0;
	fa=0;
	
	for(l=0;l<nrNivele;l++)
	{	
		
		j=0;
		while(j<=l && copac[i].nivel==l)
		{
			fructeAlese[fa++]=copac[i++].w;
			j++;
		}
		qsort(fructeAlese,fa,sizeof(int),comparare2);
		
		fa = l+1;
	}*/
	l=0;
	j=0;
	fa=0;
	for(i=0;i<N;i++)
	{
		if(copac[i].nivel==l && j<=l)
		{	
			fructeAlese[fa++]=copac[i].w;
			j++;
//			printf("b sort ");
//			for(k=0;k<fa;k++)
//				printf("%d ",fructeAlese[k]);
//			printf("\n");
			qsort(fructeAlese,fa,sizeof(int),comparare2);		
			fa=l+1;
		}
		
		if(copac[i].nivel>l)
		{
			l=copac[i].nivel;
			i--;
			j=0;
		}
//		printf("a sort ");
		
//		for(k=0;k<fa;k++)
//			printf("%d ",fructeAlese[k]);
//		printf("\n");

	}
	
	

	for(k=0;k<fa;k++)
	{	
		rezultat+=fructeAlese[k];
//		printf("\n%d ",fructeAlese[k]);
	}
	fprintf(fout,"%d",rezultat);
	
//	displayTree();
	
	fclose(fin);
	fclose(fout);
	free(copac);
	return 0;
}