Cod sursa(job #437934)

Utilizator razvan.manolescuManolescu Razvan razvan.manolescu Data 10 aprilie 2010 11:45:38
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.33 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 qsort( unsigned long h[],unsigned long w[], int l, int r){
   
int m;

 if(l<r) {
        m = part( h,w, l, r);
       qsort( h, w, l, m-1);
       qsort( 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]);

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


for(i=n-1;i>=0;i--){
					

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


maxt+=max;

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

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