Cod sursa(job #440988)

Utilizator andreeabiancaPreoteasa Andreea Bianca andreeabianca Data 12 aprilie 2010 18:30:54
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>

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



int compare ( const void *a,const void *b)
{
    gutuie g1= *((gutuie*)a );
    gutuie g2= *((gutuie*)b);
    if ( g1.rang == g2.rang )
       return g2.g-g1.g;
    return g2.rang-g1.rang;
    
}


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, rang, nr, poz;  
   gutuie g[100001];
  
   
   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[i].h), &(g[i].g) );
        g[i].rang= (h- g[i].h )/u;
   }
   qsort( g, n, sizeof(gutuie) ,  compare ) ;
   
   rang = g[0].rang;
   maxg=g[0].g;
   g[0].g=0;
   
  
   
   for ( i=rang-1; i>=0; i-- )
   {
       nr=findmax( g, n, i, &poz );
       g[poz].g=0;
       maxg+=nr;
   }
   
   fprintf( out, "%li", maxg);
   
   return 0;
}