Cod sursa(job #543165)

Utilizator Catah15Catalin Haidau Catah15 Data 27 februarie 2011 17:31:48
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <iostream>

using namespace std;

#define MAXN 18
#define INF (1LL << 50)


int n, m, a[MAXN][MAXN], x[MAXN];
long long SUM[MAXN]; 
long long maxx = - INF;

inline int negatee (int z)
{
	return - z ;
}


void solve ()
{
	long long S = 0;
	
	for (int i = 1; i <= n; ++i)
	{
		int c = SUM[i];
		
		for (int j = 1; j <= m; ++j)
			if (x[j])
				c += 2 * negatee (a[i][j]);
		
		if (c < - c)
			S += - c;
		else
			S += c;
	}
	
	if (S > maxx)
		maxx = S;

}


void back (int k)
{
	for (int i = 0; i <= 1; ++i)
	{
		x[k] = i;
		
		if (k == m)
			solve();
		else
			back (k + 1);
	}
}


int main()
{
	ifstream f("flip.in");
	ofstream g("flip.out");
	
	f >> n >> m;
	
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{	
			f >> a[i][j];
			SUM[i] += a[i][j];
		}
	
	back (1);
	
	g << maxx;
	
	f.close();
	g.close();
	
	return 0;
}