Cod sursa(job #439738)

Utilizator akan_tmCornea Alexandru akan_tm Data 11 aprilie 2010 18:52:24
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.29 kb
#include <stdio.h>

typedef struct { int h, g; } gutuie;

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


int main()
{
   long n, h, u,i, maxg=0,j, max ;   
   gutuie g[100001];
   
   
   FILE *f = fopen( "gutui.in", "rt" );
   FILE *out = fopen ( "gutui.out", "wt"); 
    
   fscanf(f, "%i %i %i", &n, &h, &u);
   
   
   for( i=0; i<n;i++ ) 
        fscanf (f, "%i %i", &(g[i].h), &(g[i].g) );

   qsort( g, n, sizeof(gutuie) ,  compare ) ;
   
   i=0;
    while ( i<n && h >0 )
    {
          if ( g[i].h > h ) i++;
          
          else if( g[i].h < h-u ) 
               {
                  maxg += 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;    
               i++;
               h=h-u;
          }
  
    }
   
   
    fprintf( out, "%i", maxg);
    getch();
    return 0;
}