Cod sursa(job #21462)

Utilizator tvladTataranu Vlad tvlad Data 23 februarie 2007 17:24:14
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>

const int N = 16;

int n,m;
int a[N][N];
int sl[N];
int sc[N];
int lin[N];
int st;
//int col[N];

inline bool bit ( int conf, int k ) {
	int aux = 1<<k;
	return ((aux & conf) != 0);
}

int suma ( int conf ) {
	int s = st;
	int rlin[N];
	int nrl = 0;
	for (int i = 0; i<n; ++i) {
		if (bit(conf,i)) {
			s -= 2*sl[i];
			rlin[nrl++] = i;
		}
	}
	for (int j = 0; j<m; ++j) {
		int ss = s - 2*sc[j];
		for (int i = 0; i<nrl; ++i) {
			ss += 2 * a[rlin[i]][j];
		}
		if (ss > s) s = ss;
	}
	return s;
}

int main() {
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	st = 0;
	if (n > m) {
		m ^= n; n ^= m; m ^= n;
		for (int j = 0; j<m; ++j) {
			for (int i = 0; i<n; ++i) {
				scanf("%d",&a[i][j]);
				st += a[i][j];
				sl[i] += a[i][j];
				sc[j] += a[i][j];
			}
		}
	} else {
		for (int i = 0; i<n; ++i) {
			for (int j = 0; j<m; ++j) {
				scanf("%d",&a[i][j]);
				st += a[i][j];
				sl[i] += a[i][j];
				sc[j] += a[i][j];
			}
		}
	}
	/*printf("%d %d\n",n,m);
	for (int i = 0; i<n; ++i) {
		for (int j = 0; j<m; ++j) {
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
	for (int i = 0; i<n; ++i) {
		printf("Suma pe linia %d este %d\n",i,sl[i]);
	}
	for (int j = 0; j<m; ++j) {
		printf("Suma pe coloana %d este %d\n",j,sc[j]);
	}*/

	int max = -2000000000, s;
	for (int conf = 0, lim = 1<<n; conf < lim; ++conf) {
		if ((s = suma(conf)) > max) max = s;
	}
	
	printf("%d\n",max);
	return 0;
}