Cod sursa(job #475348)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 6 august 2010 18:36:54
Problema Jocul Flip Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <string>

using namespace std;

#define NM 20
#define inf 2000000000

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

int main()
{
	int best = -inf;
	
	freopen ("flip.in", "r", stdin);
	freopen ("flip.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]);
			
	for (int i = 0; i < (1<<N); ++i)
	{
		int ansc = 0;	
		
		for (int col = 1; col <= M; ++col)
		{
			int minus = 0;
			int plus = 0;
			
			for (int lin = 1; lin <= N; ++lin)
			{
				if ((1<<(lin-1)) & i) A[lin][col]*=(-1);
				
				if (A[lin][col] >= 0) plus += A[lin][col];
				else minus -= A[lin][col]; 
			}	
			
			if (plus > minus) ansc += (plus-minus);
			else ansc += (minus-plus);
		}	
		
		best = max(best, ansc);
	}
	
	printf ("%d", best);
	
	return 0;
}