Cod sursa(job #1184468)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 12 mai 2014 20:00:57
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin( "elimin.in" );
ofstream fout( "elimin.out" );

const int nmax = 15;
const int mmax = 7294;
int n, m, r, c, sol;
bool scos[ nmax + 1 ];
int y[ mmax + 1 ], a[ nmax + 1 ][ mmax + 1 ];

inline void read_nbs() {
    fin>>n>>m>>r>>c;
    if ( n > 15 ) {
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= m; ++ j ) {
                fin>>a[ j ][ i ];
            }
        }
        int aux = n;
        n = m; m = aux;
        aux = r; r = c; c = aux;
    } else {
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= m; ++ j ) {
                fin>>a[ i ][ j ];
            }
        }
    }
}
void bkt( int x, int ram ) {
    scos[ x ] = 1;
    if ( ram > 0 ) {
        for( int i = x + 1; i <= n - ram + 1; ++ i ) {
            bkt( i, ram - 1 );
        }
    } else {
        int s = 0;
        for( int j = 1; j <= m; ++ j ) {
            y[ j ] = 0;
            for( int i = 1; i <= n; ++ i ) {
                if ( scos[ i ] == 0 ) {
                    y[ j ] += a[ i ][ j ];
                }
            }
            s += y[ j ];
        }
        sort( y + 1, y + m + 1 );
        for( int i = 1; i <= c; ++ i ) {
            s -= y[ i ];
        }
        if ( s > sol ) {
            sol = s;
        }
    }
    scos[ x ] = 0;
}
int main()
{
    sol = -1<<30;
    read_nbs();
    bkt( 0, r );
    fout<<sol<<'\n';
    fin.close();
    fout.close();
    return 0;
}