Cod sursa(job #553917)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 14 martie 2011 13:41:56
Problema Jocul Flip Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
using namespace std;

int n , m , x[20] , y[20] , cont;
long long a[20][20] , suma , sol[2000000] , sumap;

int valid ()
{
	for (int i = 1 ; i <= n ; ++i)
		if (x[i] != y[i])
			return 1;
	return 0;
}
void solution ()
{
	suma = 0;
	
	for (int i = 1 ; i <= n ; ++i)
	{
		y[i] = x[i];
		if (x[i] == 1)
			for (int j = 1 ; j <= m ; ++j)
				a[i][j] *= -1;
	}
	
	for (int j = 1 ; j <= m ; ++j)
	{
		sumap = 0;
		for (int i = 1 ; i <= n ; ++i)
			sumap += a[i][j];
		if (sumap < 0)
			for (int i = 1 ; i <= n ; ++i)
				a[i][j] *= -1;
	}
	
	for (int i = 1 ; i <= n ; ++i)
		for (int j = 1 ; j <= m ; ++j)
			suma += a[i][j];
	
	cont++;
	sol[cont] = suma;
}
void back (int k)
{
	for (int i = 1 ; i >= 0 ; --i)
	{
		x[k] = i;
		
		if (k == n)
		{
			if (valid())
				solution();
		}
		
		else back(k+1);
	}
}
int main ()
{
	ifstream f ("flip.in");
	ofstream g ("flip.out");
	
	long long max = 0;
	
	f >> n >> m;
	
	for (int i = 1 ; i <= n ; ++i)
		for (int j = 1 ; j <= m ; ++j)
			f >> a[i][j];
		
	back(1);
	
	for (int i = 1 ; i <= cont ; ++i)
		if (sol[i] > max)
			max = sol[i];
	
	g << max;
	return 0;
}