Cod sursa(job #440195)

Utilizator RazvanSSavu Razvan RazvanS Data 11 aprilie 2010 22:40:35
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.02 kb
#include <stdio.h>
#include <stdlib.h>

#define file_in "gutui.in"
#define file_out "gutui.out"

#define N_MAX 100000

typedef unsigned long long int ULLI;

ULLI sum_w;

struct s_gutuie {
	
	int h, w;
};

typedef struct s_gutuie* gutuie;

gutuie G[N_MAX];
int n, h_max , u;
char *V;

struct s_cell {
	
	int f_z;
	int h;
};

typedef struct s_cell* cell;

cell* C;

void init ( void ) {

	int i;
	for(i=0;i<n;++i)
		G[i] = (gutuie) calloc ( 1 , sizeof ( struct s_gutuie ) );
}

void read_input ( void ) {
	
	int i;
	FILE* fin = fopen ( file_in , "r" );
	fscanf(fin , "%d %d %d", &n , &h_max , &u);
	init ();
	for(i=0;i<n;++i) 
		fscanf(fin , "%d %d", &(G[i]->h) , &(G[i]->w) );
	fclose(fin);
}
void concat ( int a, int m, int b ) {
	
	gutuie* G_aux = (gutuie*) calloc ( b-a+1 , sizeof(gutuie) );
	int i, j, k;
	i = a; j = m+1; k = 0;

	while ( i<=m && j<= b ) 
		if ( G[i] -> w > G[j] -> w ) G_aux[k++] = G[i++];
		else G_aux[k++] = G[j++];
	
	while ( i<=m ) G_aux[k++] = G[i++];
	while ( j<=b ) G_aux[k++] = G[j++];
	
	for(i=a, k=0;i<=b;++i)
		G[i] = G_aux [k++];

	free ( G_aux );
}

void merge_sort ( int a, int b ) {
	

	if ( a < b ){
		
		int m = (a+b)/2;
		merge_sort(a,m);
		merge_sort(m+1,b);
		concat(a,m,b);
	}
}

int to_seg ( int i ) {
	
	return (h_max - G[i]->h ) / u;
}

int add_V ( int loc ) {
		
	int j;
	for(j=loc ; V[j] ; --j );
		
		if ( j >=0 )
			V[j]=1;
			
	return j;
}

void calculate ( void ) {
	
	merge_sort (0,n-1);
	
	int i;
	
	int nr_seg = h_max / u + ( (h_max%u) ? 1 : 0 );
	
	V = (char *) calloc ( nr_seg , sizeof( char ) );
	C = (cell *) calloc ( nr_seg , sizeof( cell ) );
	
	for(i=0;i<n;++i)
		if(add_V ( to_seg (i) ) >= 0 ) sum_w+=G[i]->w;
		
	free ( V );
}	

void print_rez ( void ) {
	
	FILE * fout = fopen ( file_out , "w");
	fprintf(fout, "%llu\n" , sum_w);
	fclose(fout);
}	

void end ( void ) {
	
	int i;
	for(i=0;i<n;++i)
		free ( G[i] ); 
}

void print_gutui ( void ) {
	
	int i;
	
	for (i=0;i<n;++i)
		printf("%d %d\n", G[i]->h , G[i]->w);
}

int main ( void ) {
	
	read_input ();
	calculate ();
	print_rez();

	
	return 0;
}