Cod sursa(job #438596)

Utilizator ralu_k_sSocea Raluca ralu_k_s Data 10 aprilie 2010 21:34:04
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.62 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;
	if( *(h+i) < *(h+j) )
		return 1;
	if( *(h+i) == *(h+j) )
	{	if( *(g+i) < *(g+j) )
			return 1;
		if( *(g+i) == *(g+j) )
			return 0;
	}
	return -1;	
	
}


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

	// Citire
	FILE *fin;
	fin = fopen("gutui2.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 );//raspuns: 233000000
	
	int *pas = (int *) calloc(N, sizeof(int));
	unsigned long int *val = (unsigned long int *) calloc(N, sizeof(unsigned long int));
	unsigned long int gcrt,hcrt,max;
	*pas = 1;
	*val = *(g+ *ord);
//	printf("\n%i: %lu\n",1,*val);
	for(i=1; i<N;i++)
	{	gcrt = *(g+ *(ord+i));
		hcrt = *(h+ *(ord+i));
		max = gcrt;
		*(pas+i) = 1;
		for(j=0;j<i;j++)
			if(H-(*(pas+j))*U >= hcrt && gcrt + (*(val+j)) > max)
			{	max =gcrt + (*(val+j));
				*(pas+i) = *(pas+j) + 1;
			}
	//	printf("%i: %lu\n",i+1,max);
		*(val+i) = max;
		if(max > Gmax)
			Gmax = max;
	}
		
	
	//Afisare
	FILE *fout;

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