Cod sursa(job #2694819)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 10 ianuarie 2021 19:45:26
Problema Elimin Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 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 ];
int col[ 7294 ], aux[ 7294 ];
const int MASK = BASE - 1;
int n, m, nr_lin, nr_col;
int a[ 15 ][ 7294 ];
int maxx, s;

void myswap( int &a, int &b ){
    int cop = a;
    a = b;
    b = cop;
}

void radixsort( int v[], int aux[], int n, int bits ){
    if( bits == MAX_BITS )
        return;
    for( int i = 0; i < n; i++ )
        ++freq[ v[ i ] >> 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 ] >> bits & MASK ]++ ] = v[ i ];
    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 );
    if( n > m ){
        myswap( n, m );
        myswap( nr_lin, nr_col );
    }
    for( int l = 0; l < n; l++ )
        for( int c = 0; c < m; c++ )
            fscanf( fin, "%d", &a[ l ][ c ] );
    fclose( fin );
    int pp = ( 1 << n );
    for( int i = 0; i < pp; i++ ){
        int cop = i, nr0 = 0;
        while( cop > 0 ){
            if( cop & 1 )
                ++nr0;
            cop >>= 1;
        }
        if( nr0 == nr_lin ){
            for( int bit = 0; bit < n; bit++ )
                if( ( i & ( 1 << bit ) ) == 0 )
                    for( int c = 0; c < m; c++ )
                        col[ c ] += a[ bit ][ c ];
            radixsort( col, aux, m, ( s = 0 ) );
            for( int c = 0; c < m; c++ ){
                if( c >= nr_col )
                    s += col[ c ];
                col[ c ] = 0;
            }
            if( maxx < s )
                maxx = s;
        }
    }
    FILE *fout = fopen( "elimin.out", "w" );
    fprintf( fout, "%d\n", maxx );
    fclose( fout );
    return 0;
}