Cod sursa(job #543162)

Utilizator Catah15Catalin Haidau Catah15 Data 27 februarie 2011 17:25:04
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>

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 > SUM[i])
			S += c;
		else
			S += SUM[i];
	}
	
	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;
}