Cod sursa(job #439834)

Utilizator akan_tmCornea Alexandru akan_tm Data 11 aprilie 2010 19:44:30
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.13 kb
#include <stdio.h>

typedef struct { int h, g; } gutuie;

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

int cmpint ( void *a, void *b)
{
   long i1= *((int*)a);
   long i2= *((int*)b);
   return i1-i2;
    
    
}
long findmin( long * a, long sf, long *poz )
{
    long i, min=a[0];
    for( i=1;i<sf;i++)
         if(min > a[i])
         {
                *poz=i;
                min=a[i];
         }
         
    return min;
    
}

int main()
{
   long n, h, u,i, maxg=0,j, max ;   
   gutuie g[100001];
   long ia[100001], sf=0, poz,min;
   
   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) );

   qsort( g, n, sizeof(gutuie) ,  compare ) ;
   
   i=0;
    while ( i<n && h >0 )
    {
          
          if ( g[i].h > h ) break;
          
          
          else if( g[i].h < h-u ) 
               {
                  maxg += g[i].g;
                  ia[sf++]=g[i].g;
                  i++;
                  h=h-u;
               }
          else 
          {
               j=i+1;
               max=g[i].g;
               while ( j<n )
               {
                   if( g[j].h < h-u ) break;
                   
                   if ( max < g[j].g ) max = g[j].g;
                   j++;    
                     
               } 
               
               maxg += max;
               ia[sf++]=max;    
               i++;
               h=h-u;
          }
  
    }
  //  qsort( ia, sf, sizeof(long), cmpint);
    
    for( j=i; j<n;j++ )
    {
        min=findmin( ia, sf, &poz);
        if( min < g[j].g )
        {
            //printf("%li ", poz);
            maxg= maxg - ia[poz];
            maxg+= g[j].g;  
            ia[poz]=g[j].g;
        }
         
    }
   
   
    fprintf( out, "%li", maxg);
   // getch();
    return 0;
}