Cod sursa(job #804786)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 30 octombrie 2012 14:43:45
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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],sol[N][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 msb(int val){
	int i=0;
	for(;val;i++,val=val>>1);
	return i-1;
}

int flip(int mb,int i){
	int val=0;
	for(int l=1,lin=i;lin;lin=lin>>1,l++){
		if(lin&1){
			val+=(4*a[l][mb]);
		}
	}
	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];
		}
	}
	sol[0][0]=matrixval;
	int mb;
	for(j=1;j<subcol;++j){
		mb=msb(j);
		sol[0][j]=sol[0][j^(1<<mb)]-2*sc[mb+1];
		if(sol[0][j]>result){
			result=sol[0][j];
		}
	}
	for(i=1;i<sublin;++i){
		mb=msb(i);
		sol[i][0]=sol[i^(1<<mb)][0]-2*sl[mb+1];
		for(j=1;j<subcol;++j){
			mb=msb(j);
			sol[i][j]=sol[i][j^(1<<mb)]-2*sc[mb+1]+flip(mb+1,i);
			if(sol[i][j]>result){
				result=sol[i][j];
			}
		}
	}
	out<<result;
}

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