Cod sursa(job #1017895)

Utilizator PangratieAndreiPangratie Andrei PangratieAndrei Data 28 octombrie 2013 16:46:10
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 20 ;

int N , M ;
int matIni[Nmax][Nmax] ;
int matFol[Nmax][Nmax] ;

void matChange( int sub ){

    for( int i = 0 ; i < N ; i++ )
        for( int j = 0 ; j < M ; j++ )
            if( ( 1 << i ) & sub )
                matFol[i][j] = matIni[i][j] * -1 ;
            else
                matFol[i][j] = matIni[i][j] ;

}

void maximize (){

    for( int i = 0 ; i < M ; i++ ){

        int Sum = 0 ;
        int mSum = 0 ;

        for( int j = 0 ; j < N ; j++ ){

            Sum += matFol[j][i] ;
            mSum += -matFol[j][i] ;

        }

        if( mSum > Sum )
            for( int j = 0 ; j < N ; j++ )
                matFol[j][i] = -matFol[j][i] ;

    }

}

int matSum(){

    int sum = 0 ;

    for( int i = 0 ; i < N ; i++ )
        for( int j = 0 ; j < M ; j++ )
            sum += matFol[i][j] ;

    return sum ;
}

int main()
{
    ifstream f("flip.in");
    ofstream g("flip.out");

    f >> N >> M ;

    for( int i = 0 ; i < N ; i++ )
        for( int j = 0 ; j < M ; j++ )
            f >> matIni[i][j] ;

    int maxSum = matSum();

    cout << maxSum << endl ;

    for( int i = 0 ; i < ( 1 << N ) ; i++ ){

        matChange( i );
        maximize();

        maxSum = max ( maxSum , matSum() );

    }

    g << maxSum << '\n' ;

    return 0;
}