Cod sursa(job #2389184)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 26 martie 2019 21:04:12
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>

using namespace std;

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

const int NMAX = 20;

int N, M;

int sgn[NMAX];
int mat[NMAX][NMAX];
int val_max;

void Read()
{
  fin >> N >> M;

  for( int i = 1; i <= N; ++i )
    for( int j = 1; j <= M; ++j )
      fin >> mat[i][j];

  fin.close();
}

void Check()
{
  int S = 0;

  for( int j = 1; j <= M; ++j )
  {
    int sum = 0;

    for( int i = 1; i <= N; ++i )
      sum += mat[i][j] * sgn[i];

    ( sum > 0 ) ? S += sum : S += sum * -1;
  }

  val_max = max( val_max, S );
}

void Backtrack( int K )
{
  sgn[K] = -1;

  if( K == N ) Check();
  else Backtrack( K + 1 );

  sgn[K] = 1;

  if( K == N ) Check();
  else Backtrack( K + 1 );
}

int main()
{
    Read();
    Backtrack( 1 );

    fout << val_max << '\n';

    return 0;
}