Cod sursa(job #2104322)

Utilizator robx12lnLinca Robert robx12ln Data 11 ianuarie 2018 16:14:00
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
ifstream fin("elimin.in");
ofstream fout("elimin.out");
int A[32][1024], N, M, R, C, v[32], sol, f[32];
vector<int> S;
void bk( int pos ){
    if( pos == R + 1 ){
        memset( f, 0, sizeof(f) );
        for( int i = 1; i <= R; i++ )
            f[ v[i] ] = 1;
        S.clear();
        for( int j = 1; j <= M; j++ ){
            S.push_back( 0 );
            for( int i = 1; i <= N; i++ )
                if( f[i] == 0 )
                    S.back() += A[i][j];
        }
        sort( S.begin(), S.end() );
        int sum = 0;
        for( int i = C; i < S.size(); i++ )
            sum += S[i];
        sol = max( sol, sum );
    }else{
        for( int i = v[pos - 1] + 1; i <= N; i++ ){
            v[pos] = i;
            bk( pos + 1 );
        }
    }
}
int main(){
    fin >> N >> M >> R >> C;
    if( N <= M )
        for( int i = 1; i <= N; i++ )
            for( int j = 1; j <= M; j++ )
                fin >> A[i][j];
    else{
        for( int i = 1; i <= N; i++ )
            for( int j = 1; j <= M; j++ )
                fin >> A[M - j + 1][i];
        swap( N, M );
        swap( R, C );
    }
    bk( 1 );
    fout << sol << "\n";
    return 0;
}