Cod sursa(job #1411478)

Utilizator CTI_KnightCir Constantin CTI_Knight Data 31 martie 2015 18:58:22
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
# include <fstream>
# define MAXDIM 17
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int N, M, smax = 0, sm = 0;
int V[ MAXDIM ][ MAXDIM ];
void flip ( int linie ){
    for ( int j = 1; j <= M; j++)
        V[ linie ][ j ] *= -1;
}
void sol (){
    int s = 0, i, j;
    sm = 0;
    for ( i = 1; i <= M; i++ ){
        s = 0;
        for ( j = 1; j <= N; j++ )
            s += V[ j ][ i ];
        if ( s < 0 ) 
            s =- s;
        sm += s;
    }
    if ( sm > smax ) 
        smax = sm;
}
void backtrack ( int k ){
    if ( k > N )
        sol ();
    else{
        flip ( k );
        backtrack ( k + 1 );
        flip ( k );
        backtrack ( k + 1);
    }
}
int main(){
    f >> N >> M;  
    for ( int i = 1; i <= N; i++ ) 
        for ( int j = 1; j <= M; j++ ) 
            f >> V[ i ][ j ];
    backtrack ( 1 );
    g << smax << '\n';
    return 0;
}