Cod sursa(job #441561)

Utilizator maria.eniEni Maria-Adina maria.eni Data 12 aprilie 2010 23:16:54
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.11 kb

#include <stdlib.h>
#include <stdio.h>
//#include <conio.h>


	int h[10000], g[10000], rm[10000], x[10000];
	int i, j, H, U, k;
	long int n, sum=0;


int partition( int g[], int l, int r) {
   int pivot, i, j, aux;
   pivot = g[l];
   i = l; j = r;
		
   while( 1)
   {
   	do ++i; while( g[i] <= pivot && i <= r );
   	do --j; while( g[j] > pivot );
   	if( i >= j ) break;
    aux = g[i]; g[i] = g[j]; g[j] = aux;
   	aux = h[i]; h[i] = h[j]; h[j] = aux;
   }
   aux = g[l]; g[l] = g[j]; g[j] = aux;
   aux = h[l]; h[l] = h[j]; h[j] = aux;
   return j;
}

void quickSort( int g[], int l, int r)
{
   int j;

   if( l < r ) 
   {
        j = partition( g, l, r);
       quickSort( g, l, j-1);
       quickSort( g, j+1, r);
   }	
}


int main()
{

	int aux;
	FILE* fin;
	FILE* fout;
	
	fin = fopen ("gutui.in", "r");
	fout = fopen ("gutui.out", "w");
	
	fscanf (fin, "%li %d %d", &n, &H, &U);

	for ( i=0; i<n; i++)
		fscanf ( fin, "%d %d", &h[i], &g[i] );
		
		
  quickSort( g, 0, n);
  
  for(i=0; i<n/2; i++)
  {
           aux = g[i]; g[i]=g[n-i]; g[n-i]=aux;
           aux = h[i]; h[i]=h[n-i]; h[n-i]=aux;
           }
  
  for(i=0; i<n; i++)
  {
           g[i]=g[i+1];
           h[i]=h[i+1];
           }
/*	
	for( i=0; i<n; i++)
	printf("%d ", g[i]);
	
	for( i=0; i<n; i++)
	printf("%d ", h[i]);
	*/
	
   for( i=0; i<n; i++)
           rm[i] = (H-h[i]) / U ;
     
    int max=rm[0];      
    for( i=1; i<n; i++)
      if(max < rm [i])
             max = rm[i];

    for( i=0; i<=max; i++)
         x[i] = 0;

    for( i=0; i<n; i++)
    
      if( h[i] <= H )
      {
          if( x[ (H-h[i]) / U ]==0 )
              x[ (H-h[i]) / U ] = g[i];
      }
             else
                 for ( k=((H-h[i]) / U )-1; k>=0; k--)
                     if( x[k]==0 )
                     {
                         x[ k ] = g[i];
                          break;
                      }

      for( i=0; i<=max; i++)
           sum = sum + x[i];
      fprintf(fout, "%d", sum);
		
	fclose(fin);
	fclose(fout);
//getch();
return 0;
}