Pagini recente » Cod sursa (job #1113016) | Cod sursa (job #23004) | Cod sursa (job #1154411) | Cod sursa (job #29067) | Cod sursa (job #2694759)
#include <stdio.h>
#define MAX_BITS 32
#define BIT_PER_STEP 8
const int BASE = 1 << BIT_PER_STEP;
int freq[ BASE ], ind[ BASE ];
const int MASK = BASE - 1;
struct element {
int val = 0;
short poz;
};
int n, m, nr_lin, nr_col;
int s;
void radixsort( element v[], element aux[], int n, int bits ){
if( bits == MAX_BITS )
return;
for( int i = 0; i < n; i++ )
++freq[ v[ i ].val >> bits & MASK ];
ind[ 0 ] = 0;
for( int i = 1; i < BASE; i++ ){
ind[ i ] = freq[ i - 1 ] + ind[ i - 1 ];
freq[ i - 1 ] = 0;
}
freq[ BASE - 2 ] = freq[ BASE - 1 ] = freq[ BASE ] = 0;
for( int i = 0; i < n; i++ ){
aux[ ind[ v[ i ].val >> bits & MASK ] ].val = v[ i ].val;
aux[ ind[ v[ i ].val >> bits & MASK ]++ ].poz = v[ i ].poz;
}
radixsort( aux, v, n, bits + BIT_PER_STEP );
}
int main()
{
FILE *fin = fopen( "elimin.in", "r" );
fscanf( fin, "%d %d %d %d", &n, &m, &nr_lin, &nr_col );
element lin[ n + 1 ], col[ m + 1 ], aux[ ( n >= m ? n + 1 : m + 1 ) ];
short a[ n + 1 ][ m + 1 ];
for( int l = 0; l < n; l++ )
for( int c = 0; c < m; c++ ){
fscanf( fin, "%d", &a[ l ][ c ] );
lin[ l ].val += a[ l ][ c ];
col[ c ].val += a[ l ][ c ];
s += a[ l ][ c ];
}
fclose( fin );
for( int l = 0; l < n; l++ )
lin[ l ].poz = l;
for( int c = 0; c < m; c++ )
col[ c ].poz = c;
radixsort( lin, aux, n, 0 );
for( int l = 0; l < nr_lin; l++ ){
for( int c = 0; c < m; c++ )
col[ c ].val -= a[ lin[ l ].poz ][ c ];
s -= lin[ l ].val;
}
radixsort( col, aux, m, 0 );
for( int c = 0; c < nr_col; c++ )
s -= col[ c ].val;
FILE *fout = fopen( "elimin.out", "w" );
fprintf( fout, "%d\n", s );
fclose( fout );
return 0;
}