Cod sursa(job #442040)

Utilizator maria.eniEni Maria-Adina maria.eni Data 13 aprilie 2010 20:17:43
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.72 kb

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



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


static void quickSort (int g[], int lo, int hi)
{
//  lo is the lower index, hi is the upper index
//  of the region of array a that is to be sorted
    int i=lo, j=hi;
    int x=g[(lo+hi)/2];

    //  partition
    do
    {    
        while (g[i]>x) i++; 
        while (g[j]<x) j--;
        if (i<=j)
        {
   			aux = g[i]; g[i] = g[j]; g[j] = aux;
   			aux = h[i]; h[i] = h[j]; h[j] = aux;
            i++; j--;
        }
    } while (i<=j);

    //  recursion
    if (lo<j) quickSort(g, lo, j);
    if (i<hi) quickSort(g, i, hi);
}

int main()
{

	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-1);
  
    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[ rm[i] ]==0 )
          {
              x[ rm[i] ] = g[i];
             }

      	  else if( x[ rm[i] ]!=0 )
          		for ( k= rm[i] -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, "%li", sum);
		
	fclose(fin);
	fclose(fout);
	
return 0;
}