Cod sursa(job #440870)

Utilizator razvan.manolescuManolescu Razvan razvan.manolescu Data 12 aprilie 2010 16:56:22
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.95 kb
#include <stdio.h>
#include <stdlib.h>

#define ceil(x,u) (x)%(u) > 0 ? ((x))/(u)+1 : (x)/(u)

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

typedef struct storage{
		int w;
		int id;
		}storage;

int part( int h[],int w[], int l, int r) {
   int 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( int h[],int 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 %d %d",&n,&h,&u);

int weights[n],heights[n];storage v[n];

int i=0,j,vindex=0;
int max=0, maxt=0;

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

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

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

i=0;

while(heights[i]==0){
  maxt+=weights[i]; i++; 
}

while(heights[i]<=h%u){
					  if(weights[i]>max) max=weights[i];
					  i++;
						}
maxt+=max;
max=0;
int min,jaux,count[h/u];
for(j=0;j<h/u;j++) count[j]=0;	

for(i;i<n;i++){ 
//printf("weights[i]=%d\n",weights[i]);

if(heights[i]<=h){
			   if(vindex==0) { while(vindex<h/u	&&	i<n	&& count[ h/u - (ceil(heights[i],u))]< h/u - (ceil(heights[i],u))){ //system("pause"); printf("i=%d\n",i);
			                   
			   			            					     v[vindex].w=weights[i]; 
			   			            						 v[vindex].id= h/u - (ceil(heights[i],u));
						             						 ++count[v[vindex].id];
						             						 vindex++;
						             						  i++;
									  
						  	   		  						  }
								i--;  
			               }
			   else {   jaux=0; min=v[0].w;		for(j=0;j<vindex;j++)// printf(" [%d id=%d]",v[j].w,v[j].id);system("pause");printf("\n");for(j=0;j<h/u;j++) printf("%d ",count[j]);printf("\n");	
			   
			   			for(j=0;j<vindex;j++){
			   		           if(v[j].w < min && (count[h/u - (ceil(heights[i],u))]<= h/u - (ceil(heights[i],u)) ) || ( v[j].w < min && v[j].id==h/u - (ceil(heights[i],u)) ) ) {min=v[j].w;jaux=j;}
 			                                 }

			                 if(v[jaux].w<weights[i]){ v[jaux].w=weights[i];
							 						   count[v[jaux].id]--;
														v[jaux].id=h/u-(ceil(heights[i],u));
														count[v[jaux].id]++;
													   }
						  

			   		}
			   		
	    //	printf("\n");   for(j=0;j<h/u;j++) printf("%d ",count[j]);printf("\n");	
	//	for(j=0;j<vindex;j++) printf(" [%d id=%d]",v[j].w,v[j].id);system("pause");
			   }
}
 	//   for(j=0;j<vindex;j++) printf(" [%d id=%d]",v[j].w,v[j].id);system("pause");

for(j=0;j<vindex;j++)
    maxt+=v[j].w;
			   					  
 fprintf(g,"%d",maxt);

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