Pagini recente » Cod sursa (job #398725) | Cod sursa (job #425531) | Cod sursa (job #1996688) | Cod sursa (job #1702771) | Cod sursa (job #75854)
Cod sursa(job #75854)
#include <fstream>
#include <stdio.h>
using namespace std;
#define in "flip.in"
#define out "flip.out"
#define dim 17
int N, M;
int X[dim], Sel[dim];
int A[dim][dim];
long long maxim=0, t=0, sum=0;
int Ok(int);
void Back(int);
int main()
{
X[0] = 0;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d%d", &N, &M);
for ( int i = 1; i <= N; i++ )
for ( int j = 1; j <= M; j++ )
scanf("%d", &A[i][j]), maxim += A[i][j];
for ( int i = 1; i <= N; i++ )
{
sum = 0;
for ( int j = 1; j <= M; j++ ) sum += A[i][j];
if ( sum < 0 ) sum *= -1;
t += sum;
}
if ( t > maxim ) maxim = t;
Back(1);
printf("%lld", maxim);
}
void Back(int k)
{
for ( int i = X[k-1]+1; i <= M; i++ )
{
X[k] = i;
Sel[i] = 1;
t = 0;
if ( k <= N )
{
t = 0;
for ( int i = 1; i <= N; i++ )
{
sum = 0;
for ( int j = 1; j <= M; j++ )
{
if ( Sel[j] ) sum += (-1)*A[i][j];
else sum += A[i][j];
}
if ( sum < 0 ) sum *= -1;
t += sum;
}
if ( t > maxim ) maxim = t;
if ( k < M ) Back(k+1);
}
Sel[i] = 0;
}
}