Cod sursa(job #1126640)

Utilizator horatiu13Horatiu horatiu13 Data 27 februarie 2014 08:31:37
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
/*
http://www.infoarena.ro/problema/flip
*/

#include <cstdio>
#define Nmax 17
using namespace std;

FILE *fi = fopen("flip.in", "r");
FILE *fo = fopen("flip.out", "w");

int a[Nmax][Nmax];
int l[Nmax];
int c[Nmax];
int m;
int n;
long long s = 0;
long long max = 1<<31;
int v[2*Nmax];

void citire()
{
	fscanf(fi, "%d%d", &m, &n);
	for (int i = 1; i<=m; i++)
		for (int j = 1; j<=n; j++)
		{
			fscanf(fi, "%d", &a[i][j]);
			s += a[i][j];
		}
	max = s;
}

void bt(int k)
{
	if (k <= m+n)
	for (int i = 0; i<=1; i++)
	{
		if (k <= m)
		{
			l[k] = 2*i - 1;
			for (int j = 1; j<=n; j++)
			{
				s = s - a[k][j];
				a[k][j] = l[k] * a[k][j];
				s = s + a[k][j];
			}
			if (s > max)
				max = s;
		}
		else
		{
			c[k-m] = 2*i - 1;
			for (int i = 1; i<=m; i++)
			{
				s = s - a[i][k-m];
				a[i][k-m] = c[k-m] * a[i][k-m];
				s = s + a[i][k-m];
			}
			if (s > max)
				max = s;
		}
		bt(k+1);
	}
}

int main()
{
	citire();
	bt(1);
	fprintf(fo, "%d\n", max);
	return 0;
}