Cod sursa(job #2694759)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 10 ianuarie 2021 18:18:24
Problema Elimin Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#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;
}