Cod sursa(job #440941)

Utilizator razvan.manolescuManolescu Razvan razvan.manolescu Data 12 aprilie 2010 17:55:51
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.93 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);

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],OK=1;
for(j=0;j<h/u;j++) count[j]=0;	

for(i;i<n;i++){ 

     if(heights[i]<=h){
			   if(vindex==0) { while(OK &&vindex<h/u	&&	i<n	&& count[ h/u - (ceil(heights[i],u))]<= h/u - (ceil(heights[i],u))){ 
			   				 
			                   							  int acc=1;
							  							  for(int k=h/u - (ceil(heights[i],u));k<h/u;k++){
			                      	   		   								   							  acc+=count[k];
			                      	   		   								   							  	if(acc>k+1) OK=0;
								  																			}
								                      if(OK){
			   			            					     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++){OK=1; 
			   		           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]++;
													   }
						  

			   		  }

			       }
}

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

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