Cod sursa(job #367857)
#include <iostream>
int n, m, st[ 17 ], k;
long A[ 17 ][ 17 ], smax = -999999;
void Read()
{
FILE *in = fopen( "flip.in", "r" );
fscanf( in, "%d %d", &n, &m );
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < m; j++ )
fscanf( in, "%ld", &A[ i ][ j ] );
fclose( in );
}
int Successor()
{
if ( st[ k ] < 0 )
{
st[ k ] += 2;
return 1;
}
return 0;
}
void Type()
{
int ch[ 17 ];
long s;
for ( int j = 0; j < m; j++ )
{
s = 0;
for ( int i = 0; i < n; i++ )
{
s += st[ i ] * A[ i ][ j ];
}
ch[ j ] = s < 0 ? -1 : 1;
}
s = 0;
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < m; j++ )
s += st[ i ] * A[ i ][ j ] * ch[ j ];
if ( s > smax )
smax = s;
}
void Solve()
{
int as;
k = 0;
st[ k ] = -3;
do
{
as = Successor();
if ( as )
{
if ( k == n )
Type();
else
{
k++;
st[ k ] = -3;
}
}
else
k--;
}
while ( k > 0 );
}
void Write()
{
FILE *out = fopen( "flip.out", "w" );
fprintf( out, "%ld", smax );
fclose( out );
}
int main( void )
{
Read();
Solve();
Write();
return 0;
}