Cod sursa(job #804770)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 30 octombrie 2012 14:03:21
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>

using namespace std;

ifstream in("flip.in");
ofstream out("flip.out");

const int N=17;

int n,m,result=-(1<<30),matrixval;
int a[N][N],sl[N],sc[N]; //  suma linie si suma coloana de N

void read(){
	in>>n>>m;
	int i,j;
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j){
			in>>a[i][j];
				matrixval+=a[i][j];
		}
	}
}

int flip(int i,int j){
	int val=matrixval;
	int lin=i,col=j;
	for(int l=1;lin;lin=lin>>1,l++){
		if(lin&1){
			val-=(2*sl[l]);
		}
	}
	for(int c=1;col;col=col>>1,c++){
		if(col&1){
			val-=(2*sc[c]);
		}
	}
	for(int l=1,lin=i;lin;lin=lin>>1,l++){
		if(lin&1){
			for(int c=1,col=j;col;col=col>>1,c++){
				if(col&1){
					val+=(4*a[l][c]);
				}
			}
		}
	}
	return val;
}

void solve(){
	int sublin=1<<n;
	int subcol=1<<m;
	int i,j;
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j){
			sl[i]+=a[i][j];
		}
	}
	for(i=1;i<=m;++i){
		for(j=1;j<=n;++j){
			sc[i]+=a[j][i];
		}
	}
	for(i=0;i<sublin;++i){
		for(j=0;j<subcol;++j){
			result=max(result,flip(i,j));
		}
	}
	out<<result;
}

int main(){
	read();
	solve();
	return 0;
}