Cod sursa(job #65455)

Utilizator nobodybanAna Ban nobodyban Data 10 iunie 2007 00:40:30
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>

using namespace std;

int n;
int m;

long a[17][17],b[17][17] ;

//long a[17][17];

void citire() {
	ifstream in("flip.in");
	in >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			in >> a[i][j];	
		a[i][m] = 1;
	}
	for (int j = 0; j < m; j++)
		a[n][j] = 1;
}

long suma(long a[17][17], int n, int m) {
	long s = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) 
			if (a[n][j] * a[i][m] == 1){
				s += a[i][j];
			}
			else {
				s -= a[i][j];
			}

	return s;			
}

long suma_col(int c, long a[17][17], int n, int m) {
	long s = 0;
	for (int i = 0; i < n; i++)
		if (a[i][m] == 1){
				s += a[i][c];
			}
			else {
				s -= a[i][c];
			}

	return s;			
}

void fac(long a[17][17], int n, int m) {
	for (int i = 0; i < n; i++)
		a[i][m] = 1;
	for (int i = 0; i < n; i++)
		a[n][i] = 1;
}



long actiune(long a[17][17], int n, int m) {
	long sm =  suma(a, n, m);
	
	for (long x = 0; x < (1 << n); x++) {
		long s = 0;
		for (int i = 0; i < n; i++)
			if  (x & (1 << i))
				a[i][m] = -1;
		s = 0;
		for (int j = 0; j < m; j++) {
			int s1 = suma_col(j, a, n, m);
			if (s1 < 0)
   		   		a[n][j] = -1;			
		}
		s = suma(a, n, m);
		if (s > sm)
			sm = s;
		fac(a, n, m);
	}	
	return sm;
}

void transpusa () {
	for (int i = 0; i < m; i++) 
		for (int j = 0; j < n; j++)
			b[i][j] = a[j][i];
}

int main() {
	citire();
	ofstream out("flip.out");
	long s1 =  actiune(a, n, m);
//	long s1 = 0;
	transpusa();
	long s2 =  actiune(b, m, n);
	out << (s1 > s2 ? s1 : s2); 
	out.close();
	return 0;
}