Pagini recente » Cod sursa (job #1792584) | Cod sursa (job #185153) | Cod sursa (job #547685) | Cod sursa (job #1170634) | Cod sursa (job #440317)
Cod sursa(job #440317)
#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, dim_v;
char *V;
struct s_cell {
int f_z;
struct s_cell * up;
};
typedef struct s_cell* cell;
cell* C;
cell new_cell ( void ) {
cell new_c = (cell) calloc ( 1 , sizeof ( struct s_cell ) );
return new_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;
}
cell get_cell ( int loc ) {
cell c = C[loc];
for( ; c -> up ; c = c -> up );
return c;
}
int get_f_z ( int loc ) {
return get_cell ( loc ) -> f_z;
}
void connect_cells ( int l1 , int l2 ) {
int h1, h2;
cell c1 = C[l1];
cell c2 = C[l2];
for(h1=0; c1 -> up ; c1 = c1 -> up , ++h1);
for(h2=0; c2 -> up ; c2 = c2 -> up , ++h2);
if ( h1 < h2 ) {
c1 -> up = c2;
c2 -> f_z = c1 -> f_z;
}
if ( h1 > h2 )
c2 -> up = c1;
if ( h1 == h2 ) {
cell c = new_cell ();
c -> f_z = c1 -> f_z;
c -> up = NULL;
c1 -> up = c;
c2 -> up = c;
}
}
void put_one ( int loc ) {
int st, dr;
st = (loc >0 && V[loc-1] == 1);
dr = (loc<dim_v-1 && V[loc+1] == 1 );
V[loc] = 1;
if ( st && !dr)
C[loc] = get_cell ( loc-1 );
if ( !st && dr) {
cell c = get_cell ( loc + 1);
C[loc] = c;
c -> f_z = loc-1;
}
if ( !st && !dr) {
C[loc] = new_cell ();
C[loc] -> f_z = loc-1;
C[loc] -> up = NULL;
}
if ( st && dr ) {
C[loc] = get_cell( loc - 1 );
connect_cells ( loc, loc+1 );
}
}
int search_V ( int loc ) {
if ( V[loc] == 0 ) {
put_one ( loc );
return loc;
}
if ( V[loc] == 1 ) {
int first_z = get_f_z ( loc );
if ( first_z < 0 ) return first_z;
put_one ( first_z );
return first_z;
}
return 0;
}
void calculate ( void ) {
merge_sort (0,n-1);
int i;
int nr_seg = h_max / u + ( (h_max%u) ? 1 : 0 );
dim_v = nr_seg;
V = (char *) calloc ( nr_seg , sizeof( char ) );
C = (cell *) calloc ( nr_seg , sizeof( cell ) );
for(i=0;i<n;++i)
if(search_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;
}