Cod sursa(job #440976)

Utilizator andreeabiancaPreoteasa Andreea Bianca andreeabianca Data 12 aprilie 2010 18:26:15
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.27 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],restu[100001], sf=0, poz,min, ultim, sf2=0;
   
   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 ) i++;
          
          
          else if( g[i].h < h-u ) 
               {
                  maxg += g[i].g;
                  ia[sf++]=g[i].g;
                  i++;
                  ultim=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++;
               ultim=i;
               h=h-u;
          }
  
    }
  //  qsort( ia, sf, sizeof(long), cmpint);
 
    if( ultim<n)
    for( j=ultim; 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;
}