Cod sursa(job #440067)

Utilizator razvan.manolescuManolescu Razvan razvan.manolescu Data 11 aprilie 2010 21:43:53
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.24 kb
#include <stdio.h>
#include <stdlib.h>


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]<=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++){ 

if(heights[i]<=h){
			   if(vindex==0) { while(vindex<h/u	&&	i<n	&& count[ h/u - heights[i]/u-1]< h/u - heights[i]/u){ 
			                       
			   			            					     v[vindex].w=weights[i]; 
			   			            						 v[vindex].id= h/u - heights[i]/u; 
						             						 ++count[v[vindex].id-1];
						             						 vindex++;
						             						  i++;
									  
						  	   		  						  }
								i--;	
			               }
			   else {   jaux=0; min=v[0].w;		for(j=0;j<vindex;j++) 	
			   			for(j=0;j<vindex;j++){
			   		           if(v[j].w < min && count[h/u-heights[i]/u -1]< h/u-heights[i]/u || ( v[j].w < min && v[j].id==h/u-heights[i]/u )) {min=v[j].w;jaux=j;}
 			                                 }

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

			   		}
			   		
			   }
}

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

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