Cod sursa(job #652267)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 23 decembrie 2011 18:07:23
Problema Jocul Flip Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<iostream>
using namespace std;
int a[17][17],st[17],n,m;
long sum;
void suma (int p)
{
	int i,j,niv,x,aa[17][17];
	long s,ss;
	niv=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			aa[i][j]=a[i][j];
	for(i=1;i<=n;i++) {
		if((st[niv]==i)&&(niv<=p)) {
			x=-1;
			niv++;
		}
		else x=1;
		for(j=1;j<=n;j++)
			a[i][j]=a[i][j]*x;
	}
	s=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			s=s+a[i][j];
	for(i=1;i<=m;i++) {
		ss=0;
		for(j=1;j<=n;j++)
			ss=ss+a[j][i];
		if(ss<0) 
			s=s-2*ss;
	}
	if(s>sum) 
		sum=s;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			a[i][j]=aa[i][j];
}
inline void bktr(int p)
{
	int pval;
	for(pval=st[p-1]+1;pval<=n;pval++) {
		st[p]=pval;
		suma(p);
		bktr(p+1);
	}
}
int main ()
{
	int i,j;
	ifstream f("flip.in");
	ofstream g("flip.out");
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			f>>a[i][j];
	f.close();
	bktr(1);
	g<<sum;
	g.close();
	return 0;
}