Cod sursa(job #807445)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 4 noiembrie 2012 18:50:27
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>

using namespace std;

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

const int N=17;
const int MINF=-(1<<31);

int n,m,result=-(1<<29),matrixval;
int a[N][N],sl[N],sc[N],soli[1<<N],sol[1<<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;i;i>>=1,l++){
		if(i&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]=matrixval;
	soli[0]=matrixval;
	int mb;
	for(j=1;j<subcol;++j){
		mb=msb(j);
		sol[j]=sol[j^(1<<mb)]-2*sc[mb+1];
		if(sol[j]>result){
			result=sol[j];
		}
	}
	bool isok[subcol];
	for(i=1;i<sublin;++i){
		mb=msb(i);
		sol[0]=soli[i^(1<<mb)]-2*sl[mb+1];
		if(sol[0]>result){
			result=sol[0];
		}
		soli[i]=sol[0];
		for(j=1;j<subcol;++j)isok[j]=true;
		for(j=1;j<subcol;++j){
			mb=msb(j);
			if(!isok[j^(1<<mb)]){
				continue;
			}
			sol[j]=sol[j^(1<<mb)]-2*sc[mb+1]+flip(mb+1,i);
			if(sol[j]<sol[j^(1<<mb)]){
				int cancel=1<<mb;
				for(int k=j;k<subcol;++k){
					if(k && cancel)
						isok[k]=false;
				}
				continue;
			}
			if(sol[j]>result){
				result=sol[j];
			}
		}
	}
	out<<result;
}

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