Cod sursa(job #1458720)

Utilizator valentin50517Vozian Valentin valentin50517 Data 8 iulie 2015 12:37:06
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#define LL long long
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");

int N,M, A[20][20], L[20], C[20];
bool inv[20];
long long tmp,tot,maxi;

void inversare(int i){
	L[i] *= -1;
	for(int j = 0;j<M;j++){
		A[i][j] *= -1;
		C[j] += A[i][j]*2;
		tot += A[i][j]*2;
	}
}
void solve(){
	int i,j;
	for(i = 0;i<(1<<N);i++){
		for(j = 0;j<N;j++){
			if(i & (1 << j)){
				if(!inv[j]) 
					inversare(j),
					inv[j] = 1;
			}
			else 
			if(inv[j]) inversare(j),inv[j] = 0;
		}
		
		tmp = tot;
		for(j = 0;j<M;j++){
			if(C[j] < 0){
				tmp+=C[j]*-2;
			}
		}
		if(tmp > maxi) maxi = tmp; 
	}
}

int main(){
	int i,j;
	fin >> N >> M;
	for(i = 0;i<N;i++)
		for(j = 0;j<M;j++){
			fin >> A[i][j];
			L[i] += A[i][j];
			C[j] += A[i][j];
			tot+=A[i][j];
		}
	solve();

	fout << maxi;
	return 0;
}