Cod sursa(job #440975)

Utilizator andreeabiancaPreoteasa Andreea Bianca andreeabianca Data 12 aprilie 2010 18:25:11
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 1.89 kb
#include <stdio.h>
#include <stdlib.h>

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

int compare ( const void *a,const void *b)
{
   return *((long*)a) - *((long*)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[1700][300], rangmax=0, nr[1700], 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 ]++;
       // printf("%li ", g.rang);
        if( rangmax < g.rang) rangmax=g.rang;
   }
   
   rangmax++;
   for( i = 0; i<rangmax; i++ )
        if( nr[i]>0 )
            qsort( m[i], nr[i], sizeof(long) ,  compare ) ;
   
  
  /*
   for( i=0; i < rangmax; i++ )
   {
        printf("nivelul %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-- )
   {
           max=0;
           poz=0;
           for ( j=rangmax-1; j>= i; j-- )
               if( j>=0 && nr[j]>0)
                   if( max < m[j][nr[j]-1] )
                   {
                       max=m[j][ nr[j]-1 ];
                       poz=j;
                   }
               
           maxg+=max;
           nr[poz]--;
          // k++;
       
   }

  

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