Cod sursa(job #437774)

Utilizator marina.cioceaMarina Ciocea marina.ciocea Data 10 aprilie 2010 01:37:17
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 1.38 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	long height, weight;			
    long level;
} Gutuie;

int compareH (const void * a, const void * b)
{
    Gutuie *g1=(Gutuie *)a;
    Gutuie *g2=(Gutuie *)b;
	if(((g1->height) - (g2->height))<0)
		return -1;
    return 1;
}


int main()
{
	int  i, max, current, index;
	long N=0, H=0, U=0, sum=0;
	Gutuie *gutui;

	FILE * in = fopen("gutui.in", "r");
	if(in==NULL)
		return 1;	

	fscanf(in, "%ld", &N);
	fscanf(in, "%ld", &H);
	fscanf(in, "%ld", &U);

	gutui=(Gutuie*)malloc(N*sizeof(Gutuie));
	
	for(i=0; i<N; i++)
	{
		fscanf(in, "%ld", &gutui[i].height);
        fscanf(in, "%ld", &gutui[i].weight);
		gutui[i].level=(H-gutui[i].height)/U + 1;
	}
	fclose(in);
	
	qsort (gutui, N, sizeof(Gutuie), compareH);
    while(1)
    {   
        i=0;
		while( gutui[i].level==0 && i<N )
			i++;
		if(i==N)
            break;
		current=gutui[i].level;
		index=i;
		max=gutui[i].weight;
		while((gutui[i].level==current || gutui[i].level==0) && i<N)
		{
			if(gutui[i].level==0)
				i++;
			else
			{
                gutui[i].level--;
				if(gutui[i].weight>max)
				{
					max=gutui[i].weight;
					index=i;
				}
				i++;
			}
		}
		gutui[index].level=0;
		sum+=max;
	}
	FILE * out = fopen("gutui.out", "w");
	fprintf(out, "%ld", sum);
	fclose(out);

//	getch();
	free(gutui);
	return 0;
}