Cod sursa(job #383196)

Utilizator zalmanDanci Emanuel Sebastian zalman Data 15 ianuarie 2010 23:07:23
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#define NMAX 20
/*
1 -> -
0 -> +
*/
using namespace std;

int s[NMAX], a[NMAX][NMAX], M, N, i, j, smax;

void read(void)
{
	freopen("flip.in", "r", stdin);
	scanf("%d%d", &N, &M);
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= M; ++j)
			scanf("%d", &a[i][j]);
}
void calc(void)
{
	int w[NMAX], aux[NMAX][NMAX];
	int si;
	for(i = 1; i <= N; ++i)
		if(s[i])
			for(j = 1; j <= M; ++j)
				aux[i][j] = -a[i][j];
		else
			for(j = 1; j <= M; ++j)
				aux[i][j] = a[i][j];
			
		for(j = 1; j <= M; ++j)
		{
			si = 0;
			for(i = 1; i <= N; ++i)
				si += aux[i][j];
			
			if(si > 0)
				w[j] = 1;
			else
				w[j] = -1;
			
		}		
	si = 0;
	
	for(j = 1; j <= M; ++j)
		for(i = 1; i <= N; ++i)
			si += w[j] * aux[i][j];
	
	if(si > smax)
		smax = si;
		
}
void back(int k)
{
	for(int i = 0; i <= 1; ++i)
	{
		s[k] = i;
		if(k == N)
			calc();
		else
			back(k+1);
	}
}
void print(void)
{
	freopen("flip.out", "w", stdout);
	printf("%d", smax);
}
int main(void)
{
	read();
	back(1);
	print();
	
	return 0;
}