Cod sursa(job #2680607)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 3 decembrie 2020 19:38:20
Problema Elimin Scor 40
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <stdio.h>
#define MAX_N 15
#define MAX_M 7294
#define MAX_B 32
#define GRUP_B 8
#define MASK 255
int mat[MAX_N][MAX_M], v[MAX_N], v_aux[MAX_N], f[MASK + 1];
void sort( int n ) {
    int t, aux, bit, i;
    for ( bit = 0; bit < MAX_B; bit += GRUP_B ) {
        for( i = 0; i <= MASK; i++ )
            f[i] = 0;
        for ( i = 0; i < n; i++ )
            f[v[i] >> bit & MASK]++;
        t = f[0];
        f[0] = 0;
        for ( i = 1; i <= MASK; i++ ) {
            aux = f[i];
            f[i] = f[i - 1] + t;
            t = aux;
        }
        for( i = 0; i < n; i++ )
            v_aux[f[v[i] >> bit & MASK]++] = v[i];
        for( i = 0; i < n; i++ )
            v[i] = v_aux[i];
    }
}
int main() {
    FILE *fin, *fout;
    int n, m, r, c, maxs, s, a, b1, aux, col, i, j;
    fin = fopen( "elimin.in", "r" );
    fscanf( fin, "%d%d%d%d", &n, &m, &r, &c );
    for ( i = 0; i < n; i++ ) {
        for ( j = 0; j < m; j++ ) {
            if ( n > m )
                fscanf( fin, "%d", &mat[j][i] );
            else
                fscanf( fin, "%d", &mat[i][j] );
        }
    }
    if ( n > m ) {
        aux = n;
        n = m;
        m = aux;
        aux = r;
        r = c;
        c = aux;
    }
    fclose( fin );
    maxs = 0;
    for ( i = 0; i < (1 << n); i++ ) {
        a = i;
        b1 = 0;
        while ( a > 0 ) {
            if ( a & 1 )
                b1++;
            a >>= 1;
        }
        if ( b1 == r ) {
            for( col = 0; col < m; col++ )
                v[col] = 0;
            for( j = 0; j < n; j++ ) {
                if( (i & (1 << j)) == 0 ) {
                    for( col = 0; col < m; col++ )
                        v[col] += mat[j][col];
                }
            }
            sort( m );
            s = 0;
            for( j = c; j < m; j++ )
                s += v[j];
            if ( s > maxs )
                maxs = s;
        }
    }
    fout = fopen( "elimin.out", "w" );
    fprintf( fout, "%d", maxs );
    fclose( fout );
    return 0;
}