Cod sursa(job #440750)

Utilizator akan_tmCornea Alexandru akan_tm Data 12 aprilie 2010 14:40:43
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.73 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct node 
{
 long g;
 struct node *next;
 } nod; 
 
void add( nod **p, long k)
{
     nod *q, *r;
   
        q=*p;
        if( k> q->g )
        {
            q=(nod*) malloc ( sizeof( nod ));
            q->g=k;
            q->next=*p;
            *p=q;    
            
        }
        else 
        {
            while ( q->next !=NULL )
            {
                  if( k > q->next->g ) break;
                  q=q->next;
            }
        
            r=(nod*) malloc ( sizeof ( nod));
            r->g=k;
            r->next=q->next;
            q->next=r;
        }

}


int main()
{
   long n, h, u,i, maxg=0,  poz,j, gh, gg, rang, rangmax=0, max;  
     
   nod* q[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", &gh, &gg );
        rang= (h- gh )/u;
       
        if ( q[rang] == NULL )
        {
           q[rang]=(nod *) malloc(sizeof (nod) );
           q[rang]->next=NULL;
           q[rang]->g=gg;
           
        }
        else add( &q[rang] , gg);
        if( rangmax < rang) rangmax=rang;
   }

   for ( i=rangmax ; i>=0 ; i-- )
   {
           max=0;
           poz=-1;
           for ( j=rangmax; j>= i; j-- )
               if( q[j]!= NULL )
                   if( max < q[j]->g )
                   {
                       max=q[j]->g;
                       poz=j;
                   }
               
           maxg+=max;
           if( poz != -1 ) q[poz]=q[poz]->next;

   }

   fprintf( out, "%li", maxg);
  

   return 0;
}