Cod sursa(job #70438)

Utilizator zobicaMarin Marin zobica Data 5 iulie 2007 22:28:13
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>

using namespace std;

int n;
int m;

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];		
	}
	
}

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;			
}

long suma_lin(int l, long a[17][17], int n, int m) {
	long s = 0;
	for (int j = 0; j < m; j++)
		if (a[n][j] == 1){
			s += a[l][j];
		}
		else {
			s -= a[l][j];
		}
		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 < m; i++)
		a[n][i] = 1;
}



long actiune(long a[17][17], int n, int m) {
	long sm =  suma(a, n, m);
	fac(a, n, m);
	if (n > m) {
		// linii
		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;
			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;
	}

	//coloane
	

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


int main() {
	citire();
	ofstream out("flip.out");
	out << actiune(a, n, m); 
	out.close();
	return 0;
}