Cod sursa(job #612564)

Utilizator JBaccountCatalin JBaccount Data 8 septembrie 2011 18:36:18
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>

using namespace std;

#define NM 17
#define inf 2000000000

int N, M, A[NM][NM];

int f2N()
{
	int best = -inf;
	
	for (int conf = 0; conf < (1<<N); ++conf)
	{
		int tsum = 0;
		
		for (int j = 0; j < M; ++j)
		{
			int csum = 0;
			
			for (int i = 0; i < N; ++i) 
				if ((1<<i) & conf) csum -= A[i][j];
				else csum += A[i][j];
				
			if (csum < 0) tsum -= csum;
			else tsum += csum;	
		}	
		
		best = max (best, tsum);
	}	
	
	return best;
}

int f2M()
{
	int best = -inf;
	
	for (int conf = 0; conf < (1<<M); ++conf)
	{
		int tsum = 0;
		
		for (int i = 0; i < N; ++i)
		{
			int csum = 0;
			
			for (int j = 0; j < M; ++j) 
				if ((1<<j) & conf) csum -= A[i][j];
				else csum += A[i][j];
				
			if (csum < 0) tsum -= csum;
			else tsum += csum;
		}	
		
		best = max (best, tsum);
	}	
	
	return best;
}

int main()
{
	freopen ("flip.in", "r", stdin);
	freopen ("flip.out", "w", stdout);
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j) scanf ("%d", &A[i][j]);

	int ans;
	
	if (N < M) ans = f2N();
	else ans = f2M();	
	
	printf ("%d", ans);
	
	return 0;
}