Cod sursa(job #440309)

Utilizator akan_tmCornea Alexandru akan_tm Data 11 aprilie 2010 23:40:24
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 1.94 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct { long h, g, rang; } gutuie;



int compare ( const void *a,const void *b)
{
   return *((int*)a) - *((int*)b);
}


long findmax( gutuie *g, long n, long rang , long* poz) 
{
     long i;
     long max=0;     
     *poz = 0;
     
     for ( i=0; i < n ; i++ )
     {
         if( g[i].rang < rang ) return max;
         if ( max < g[i].g )
         {
              max=g[i].g;
              *poz=i;
         }
     }
     
return max;
     
     
}

int main()
{
   long n, h, u,i, maxg=0,  poz,j;  
  // gutuie g[100001];
   gutuie g;
   long m[500][500], rangmax=0, nr[500], k=0, max;
   
   FILE *f = fopen( "gutui.in", "rt" );
   FILE *out = fopen ( "gutui.out", "wt"); 
    
   fscanf(f, "%li %li %li", &n, &h, &u);
   
   
   for( i=0; i<n;i++ ) 
   {
        fscanf (f, "%li %li", &g.h, &g.g );
        g.rang= (h- g.h )/u;
        m[g.rang][ nr[g.rang] ] = g.g;
        nr[ g.rang ]++;
        if( rangmax< g.rang) rangmax=g.rang;
   }
   for( i = 0; i<=rangmax; i++ )
        qsort( m[i], nr[i], sizeof(int) ,  compare ) ;
   rangmax++;
   //printf("%li\n\n", rangmax );
   /*
   for( i=0; i<= rangmax; i++ )
        printf("%li ", nr[i]);
      
   for ( i=0 ; i<= rangmax; i++ )
   {
       printf("\n\nnivelul %li\n", i);
       for( j=0; j <= nr[i]; j++ )     
            printf("%li ", m[i][j] );
   }
   printf("\n\n" );
   */
   
   for ( i=rangmax-1 ; i>=0 ; i-- )
   {
       poz=i;
       max=m[i][ nr[i]-1 ];
      
       for ( j=rangmax-1; j> rangmax-k-1; j-- )
           if( nr[j]>0 && max < m[j][nr[j]-1] )
           {
               max=m[j][ nr[j]-1 ];
               poz=j;
           }
           
       maxg+=max;
      // printf("max %li la nivel %li\n", maxg, i );
       nr[poz]--;
       k++;
   }

  
  // printf("%li", maxg);
   
   fprintf( out, "%li", maxg);
  // getch();
   return 0;
}