Cod sursa(job #438475)

Utilizator ralu_k_sSocea Raluca ralu_k_s Data 10 aprilie 2010 19:53:35
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.49 kb
#include<stdio.h>
#include<stdlib.h>
unsigned long int *h, *g, U;

int compare (const void * a, const void * b)
{
	int i = *(int*)a, j = *(int *)b;
	unsigned long int hi = (*(h+ i)-1)/U;		
	unsigned long int hj = (*(h+ j)-1)/U;	
	if( *(g+i) < *(g+j) )
		return 1;
	if( *(g+i) == *(g+j) )
	{	if( hi > hj)
			return 1;
		if(hi == hj)
			return 0;
	}
	return -1;	
	
}


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

	// Citire
	FILE *fin;
	fin = fopen("gutui.in","rt");
	fscanf(fin,"%i %lu %lu",&N, &H, &U);
	
	// Alocare vectori de dimensiune N (greutatile si inaltimile gutuielor)	
	g = (unsigned long int *) calloc(N, sizeof(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);
	qsort(ord, N, sizeof(int), compare);	
		
//	for(i=0;i<N;i++)
//		printf("%i ", *(ord+i)+1 );
	i=0;
	int 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)));
		}

		}
	}
	
	


	//Afisare
	FILE *fout;

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