Cod sursa(job #438128)

Utilizator razvan.manolescuManolescu Razvan razvan.manolescu Data 10 aprilie 2010 15:10:58
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.82 kb
#include <stdio.h>
#include <stdlib.h>

FILE *f,*g;
int n;
unsigned long h,u;

//void quickSort( int[], int, int);
//int part( int[], int, int);

int part( unsigned long h[],unsigned long w[], int l, int r) {
   unsigned long pivot;
   int  i, j, aux;
   pivot = h[l];
   i = l; j = r+1;
		
   while(1)
   {
   	do ++i; while( h[i] <= pivot && i <= r ) ;
   	do --j; while( h[j] > pivot );
   	
   	if( i >= j ) break;
   	aux = h[i]; h[i] = h[j]; h[j] = aux;
    aux = w[i]; w[i] = w[j]; w[j] = aux;
   }
   aux = h[l]; h[l] = h[j]; h[j] = aux;
   aux = w[l]; w[l] = w[j]; w[j] = aux;

   return j;
}

void quickSort( unsigned long h[],unsigned long w[], int l, int r){
   
int m;

 if(l<r) {
        m = part( h,w, l, r);
       quickSort( h, w, l, m-1);
       quickSort( h,w,  m+1, r);
   }	
}


int main(){

f=fopen("gutui.in","r");
g=fopen("gutui.out","w");
fscanf(f,"%d %lu %lu",&n,&h,&u);

unsigned long weights[n],heights[n];

int i;
unsigned long max=0, maxt=0;

for(i=0;i<n;i++)
fscanf(f,"%lu %lu",&heights[i],&weights[i]);

//for(i=0;i<n;i++)
//   printf(" [h=%d  w=%d]",heights[i],weights[i]);

quickSort(heights,weights,0,n-1);

/*printf("\n\n");
//print
for(i=0;i<n;i++)
   printf(" [h=%d  w=%d]\n",heights[i],weights[i]);
system("pause");*/

for(i=n-1;i>=0;i--){
      if(heights[i]<=h){
                     
   					 if(heights[i] <= h-u ) { //printf("\n[%d] [h=%d]",max,h);
  				   	   	 		   	  	  	 maxt+=max;
                            				 max=0;
                                            }
                        
                                           
                       
		         h=((heights[i]/u)+1)*u; 
                 if(weights[i]>max) max=weights[i];
        }
}
//system("pause");
//maxt+=max;printf("\n[%d] [h=%d] maxt=%d",max,h,maxt);
//system("pause");
 fprintf(g,"%lu",maxt);

 fclose(f);
 fclose(g);
 
return 0;
}