Cod sursa(job #438707)

Utilizator razvan.manolescuManolescu Razvan razvan.manolescu Data 10 aprilie 2010 23:11:22
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.71 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,j,k,maxfreeb,kaux,myh=0;
unsigned long max=0, maxt=0;

for(i=0;i<n;i++)
fscanf(f,"%lu %lu",&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");*/
int h2=h;

for(i=n-1;i>=0;i--){
      if(heights[i]<=h&&weights[i]|| heights[i]<=u && weights[i]){
		 	  			h2=((heights[i]/u)+1)*u; 
		 	  			//	printf("\n he=%d  h=%d  h2=%d",heights[i],h,h2);  system("pause");	
		 	  		//	printf("\n!!!!!!h/u-h2/u=%d h/u=%d  h2/u=%d\n\n",h/u-h2/u,h/u,h2/u);
		 	  			if( h/u - h2/u>=1){ printf("!!");
								for(j=h/u-h2/u;j>0;j--){ maxfreeb=0;
								 						  for(k=i;k>=0;k--){
								 						      			   if(weights[k]>maxfreeb){ maxfreeb=weights[k];
								 						       			                             kaux=k; 
      																	 		                  }
											  						      }
								 						    weights[kaux]=0;
															 maxt+=maxfreeb;  
														    h-=u;
														 }
							  
                          
							          }
                     
   				 
					 	 
					 		  if(heights[i] <= myh-u &&weights[i] ) {
  				          				   	     maxt+=max;//printf("\n maxt=%d max=%d",maxt,max);
                   	       						  max=0;
                   	       						  h-=u;
                           		   
					     } 
					      myh=((int)(heights[i]/u)+1)*u;
                        if(weights[i]>max) max=weights[i]; 
						
                    }                   
                       
		//	for(int i2=0;i2<n;i2++)
           //                 printf("\n [h=%d  w=%d]",heights[i2],weights[i2]);		   
			  
                 
   }


//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;
}