Cod sursa(job #437916)

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

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


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;
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);


for(i=n-1;i>=0;i--){
  if(heights[i] <= h-u ) {
  				           if(max){maxt+=max;
                                  h-=u;
                            	  max=0;
                           		   }
					     }
  if(weights[i]>max) max=weights[i];
}

maxt+=max;

 fprintf(g,"%lu",maxt);

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