Pagini recente » Cod sursa (job #2368351) | Cod sursa (job #440195)
Cod sursa(job #440195)
#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;
}