Cod sursa(job #436080)

Utilizator ralu_k_sSocea Raluca ralu_k_s Data 8 aprilie 2010 01:43:18
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.67 kb
#include<stdio.h>
#include<stdlib.h>

void sort(unsigned long int *h, unsigned long int *g, int *ord, int N,unsigned long int U)
{
	int i,j, hi,hj;
	unsigned long int aux;
	for(i=0;i<N-1;i++)
		for(j=i+1;j<N;j++)
		{	hi = (*(h+ *(ord+i))-1)/U;		
			hj = (*(h+ *(ord+j))-1)/U;	
			if( *(g+*(ord+i)) < *(g+*(ord+j) ) || *(g+*(ord+i)) == *(g+*(ord+j) ) && hi > hj)
			{	aux = *(ord+i);
				*(ord+i) = *(ord+j);
				*(ord+j) = aux;
			}	
		}


}

int main()
{	
	unsigned long int H, U, sum = 0, Gmax=0;
	int N;

	// Citire
	FILE *fin;
	fin = fopen("gutui.in","rt");
	fscanf(fin,"%lu %lu %lu",&N, &H, &U);
	
	// Alocare vectori de dimensiune N (greutatile si inaltimile gutuielor)	
	unsigned long int *g = (unsigned long int *) calloc(N, sizeof(unsigned long int));
	unsigned long int *h = (unsigned long int *) calloc(N, sizeof(unsigned long int));


	char *v = (char *) calloc(N,sizeof(char));
	int *ord = (int *) calloc(N, sizeof(int));
	int i,j;
	for(i=0;i<N;i++)
	{	fscanf(fin,"%lu %lu",h+i, g+i);
		*(ord+i) = i;
	}

	fclose(fin);
	
	sort(h,g,ord, N,U);
	
//	for(i=0;i<N;i++)
//		printf("%i ", *(ord+i)+1 );
	i=0;
	int k, niv = (H-1)/U;
	while(*(h+*(ord+i)) > H)
		i++;
	for(;i < N;i++)
	{	j = (*(h+*(ord+i)) - 1)/U;
		if( j<=niv)
		{
//		printf("j start: %i\n",j);
		while((*(v+j)) == 1 && j< niv)
			j++;
//		printf("j final: %i\n",j);
		if(!(*(v+j)) && *(g+*(ord+i)) <= j*U)
		{		
			*(v+j) = 1;
			Gmax = Gmax + (*(g+*(ord+i)));
//			printf("adauga: %i\n",*(g+*(ord+i)));
		}
//		for(k=0;k<H/U;k++)
//			printf("%i ", *(v+k));
//		printf("\n");	
		}
	}
	
	


	//Afisare
	FILE *fout;

	fout = fopen("gutui.out","wt");
	fprintf(fout,"%lu", Gmax);
//	printf("\n%lu\n", Gmax);
	fclose(fout);
	return 0;
}