Cod sursa(job #436632)

Utilizator adriana89Adriana adriana89 Data 8 aprilie 2010 18:35:24
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.32 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;

int N ;
int H , U;

typedef struct gutui
		{
		int *g;
		int nr;
		} GUTUI;
GUTUI *G;
int nr_nivele;
int nivel( int h )
{
return ( H - h ) / U;
}
/* void interc ( int l , int m , int r , int **a)
{
int i ,j ,k ,t , b[10000];
for ( i = l ; i <= r ; i++)
	b[i] = (*a)[i];
i = l ;
j = m ;
k = l ;
while ( i <= m && j <= r)
	if ( b[i] < b[j] )
		(*a)[k++] = b[j++];
		else
			(*a)[k++] = b[i++];
for ( t = i ; t <= m ; t++)
	(*a)[k++] = b[t];
for ( t = j ; t <= r ; t++)
	(*a)[k++] = b[t];
}
void mergesort ( int l , int r , int **a )
{
int m;
if ( l == r ) return;
m = ( l + r ) / 2 ;
mergesort( l , m , a);
mergesort( m+1 , r , a);
interc ( l , m , r , a);
} */
void mergesort( int low, int high , int *a) {
 int i = 0;
 int length = high - low + 1;
 int pivot  = 0;
 int merge1 = 0;
 int merge2 = 0;
 int working[length];

 if(low == high)
  return;

 pivot  = (low + high) / 2;

 mergesort(low, pivot, a);
 mergesort( pivot + 1, high, a);
 
 for(i = 0; i < length; i++)
  working[i] = a[low + i];

 merge1 = 0;
 merge2 = pivot - low + 1;

 for(i = 0; i < length; i++) {
  if(merge2 <= high - low)
   if(merge1 <= pivot - low)
    if(working[merge1] < working[merge2])
     a[i + low] = working[merge2++];
    else
     a[i + low] = working[merge1++];
   else
    a[i + low] = working[merge2++];
  else
   a[i + low] = working[merge1++];
 }
}
void citire()
{
int i , h , gre , niv , n ;
nr_nivele = 0;
FILE *f = fopen ( "gutui.in" , "r" ) ;
fscanf( f , "%d%d%d", &N , &H , &U) ;
G = ( GUTUI * ) malloc ( ( H / U + 1 ) * sizeof ( GUTUI ) ) ;
for ( i = 0 ; i < H / U ; i++ )
	{
	G[i].g = NULL ;
	G[i].nr = 0;
	}
for ( i = 0 ; i < N ; i++ )
	{
	fscanf ( f , "%d%d" , &h , &gre ) ;
	niv = nivel ( h );
	n = G[niv].nr;
	G[niv].g = ( int * ) realloc ( G[niv].g , ( n + 2 ) * sizeof ( int ) ) ;
	G[niv].g[n] = gre;
	G[niv].nr = G[niv].nr + 1;
	}
nr_nivele = H / U;
if ( H % U != 0)	
	nr_nivele++;

fclose ( f );
}

int compar (const void * x, const void * y) 
{
  return ( * ( int * ) y - * ( int * ) x );
}

bool compare(unsigned int a, unsigned int b)	{
    return a > b;
}

void rezolva()
{

int suma = 0;
int i , j , k , l = 0;
//int *max = (int *) malloc (10000 * sizeof ( int ) );
vector<int> max;
for (i = 0 ; i < nr_nivele ; i++) 
	qsort ( G[i].g , G[i].nr , 4 , compar );
	/*if (G[i].nr > 1)
	mergesort( 0 , G[i].nr - 1 , G[i].g );*/
for (i = 0 ; i < nr_nivele ; i++) 
	{
	j = i + 1;
	if (G[i].nr != 0) 
		{
		for (k = 0 ; k < j ; k++) 
			if ( ( G[i].nr - k ) > 0 ) 
				max.push_back(G[i].g[k]);
				else
				break;
			inplace_merge ( max.begin(), max.end() - k, max.end(), compare );
			max.resize(j);
			//qsort ( max , l , 4 , compar );
			//mergesort( 0 , l - 1 , max );
			if (l > j) 
				l = j;
		}
	}
for ( i = 0 ; i < (int) max.size() ; i++)
	suma = suma + max[i];
FILE *f = fopen ( "gutui.out" , "w" ) ;
fprintf ( f , "%d\n" , suma );
fclose(f);
}

int main()
{
citire();
rezolva();
/* int *a= (int * )malloc(400),i;
for (i = 0 ; i < 20 ; i++)
	a[i]=rand()%100;
for (i = 0 ; i < 20 ; i++)
	printf("%d \n",a[i]);
mergesort(0,19,a);
for (i = 0 ; i < 20 ; i++)
	printf("aaaaa%d \n",a[i]); */
return 0;
}