Cod sursa(job #439687)

Utilizator catamihaCatalina Nita catamiha Data 11 aprilie 2010 18:21:28
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.79 kb

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int *sol;
typedef struct
	{
    unsigned int poz; 
    unsigned int val; 
   
} valminime;

typedef struct info_gutuie 

 {unsigned int h;

  unsigned int g; 

   } GUTUIE;

GUTUIE *gutuie;

int minim (int k)

{ int i,min,poz=0;
  min=sol[0];
	for (i=1;i<k;i++)
            if (min>sol[i]) 
                    {min=sol[i]; poz=i;}
     return poz;}

int relatie (GUTUIE *nr1, GUTUIE *nr2)

    	{ 
	  if ((*nr1).h < (*nr2).h) {/*printf ("%u %u\n", nr1->g, nr2->g);*/ return 1;}

          if ((*nr1).h > (*nr2).h) return -1;

          if ((*nr1).h == (*nr2).h) {  if ((*nr1).g < (*nr2).g ) return 1;

                                       if ((*nr1).g == (*nr2).g) return 0;

                                       if ((*nr1).g>(*nr2).g)  return -1;
					}
	}
int main()
{
unsigned int n,h,u;

long int suma=0;

int i,j,m,k,nrg,min,culese=0;

FILE *in, *out;

	in=fopen ("gutui.in", "r");

	out=fopen ("gutui.out","w");

fscanf (in,"%u",&n);

//printf ("%u ", n);
valminime *vmin;
gutuie =(GUTUIE*) calloc (n,sizeof (GUTUIE));

sol=(int *) calloc(n,sizeof(int));

vmin=(valminime*) calloc (n,sizeof(valminime));

fscanf (in,"%u",&h);

fscanf (in,"%u", &u);

	for (i=0;i<n;i++)

		{fscanf (in,"%u", &gutuie[i].h);
		 fscanf (in,"%u",&gutuie[i].g);}
//printf ("%d", n);
j=0;
min=0;
	  qsort(gutuie,n,sizeof(GUTUIE),(void*) relatie);

   // for (i=0; i<n;i++)
     // printf ("%u %u\n", gutuie[i].g,gutuie[i].h);
	
	for (i=0;i<n;i++)
		
	{	if (gutuie[i].g>vmin[j].val)
			{sol[vmin[j].poz]=gutuie[i].g; 
                         j--; }
                else
		   {sol[culese++]=gutuie[i].g; vmin[j+1].val=gutuie[i].g; vmin[j+1].poz=i; j++;}	}
           
      for (i=0;i<culese;i++)
          suma=suma+sol[i];
fprintf(out,"%ld",suma);
   return 0;}