Cod sursa(job #29004)

Utilizator victor_u_roVictor Ungureanu victor_u_ro Data 8 martie 2007 15:16:25
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <string.h>

#define NMAX 32
#define max(a, b) (a > b ? a : b)

long a[NMAX][NMAX], b[NMAX][NMAX], smax;
int n, m;

void cit() {
	freopen("flip.in", "rt", stdin);
	int i, j;

	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			scanf("%ld", &a[i][j]);

	fclose(stdin);
}

void rez() {
	int v[NMAX], i, j, k, kf;
	long s[NMAX], ss;

	memset(v, 0, (n + 1) * sizeof(v[0]));
	kf = 1 << n;
	for (k = 1; k <= kf; k++) {
		for (i = 1; i <= n; i++) {
			memcpy(b[i], a[i], (m + 1) * sizeof(a[i][0]));
			if (v[i])
				for (j = 1; j <= m; j++)
					b[i][j] = -b[i][j];
		}
		for (j = 1; j <= m; j++) {
			ss = 0;
			for (i = 1; i <=n; i++)
				ss += b[i][j];
			s[j] = max(ss, -ss);
		}
		ss = 0;
		for (j = 1; j <= m; j++)
			ss += s[j];
		if (ss > smax)
			smax = ss;
		v[1]++;
		ss = v[1] >> 1;
		v[1] &= 1;
		for (i = 2; i <= n; i++) {
			v[i] += ss;
			ss = v[i] >> 1;
			v[i] &= 1;
		}
	}
}

void afis() {
	freopen("flip.out", "wt", stdout);

	printf("%ld\n", smax);

	fclose(stdout);
}

int main() {
	cit();
	rez();
	afis();

	return 0;
}