Cod sursa(job #161737)

Utilizator reSpawnPopescu Ioan reSpawn Data 18 martie 2008 19:08:03
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
int st[20];
int sMax = -100000000;

int N, M;
int tabla[20][20];

void check()
{
	static int suma, X;
	static int i, j;
	suma = 0;
	for( i = 0; i < N; ++i )
	{
		X = 0;
		for( j = 0; j < M; ++j )
			X += st[j] * tabla[i][j];
		if( X > 0 )
			suma += X;
		else
			suma += -X;
	}
	if( suma > sMax )
		sMax = suma;
}

void backtrack( int k )
{
	if( k >= M )
		check();
	else
	{
		st[k] = 1;
		backtrack( k + 1 );
		st[k] = -1;
		backtrack( k + 1 );
	}
}
		

int main()
{
	freopen( "flip.in", "r", stdin );
	freopen( "flip.out", "w", stdout );

	scanf("%d %d", &N, &M);
	int i,j;
	for(i = 0; i < N; ++i)
		for(j = 0; j < M; ++j)
			scanf("%d", &tabla[i][j]);

	backtrack( 0 );
	printf("%d", sMax );
	return 0;
}