Cod sursa(job #613979)
#include <fstream>
using namespace std;
int st[100],k,m,n;
long long int s,smax=0,a[17][17];
ofstream g ("flip.out");
void init()
{
st[k]=-1;
}
int am_succesor()
{
if(st[k]<1)
{
st[k]++;
return 1;
}
return 0;
}
int e_valid()
{
if(k==n+m)
{
s=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(((st[i]==0)&&(st[n+j]==0))||((st[i]==1)&&(st[n+j]==1))) s+=a[i][j];
else s+=-a[i][j];
}
}
return 1;
}
int solutie()
{
return k==n+m;
}
void afis()
{
if(s>smax) smax=s;
}
void back()
{
int as; k=1; init();
while(k>0)
{
do{} while((as=am_succesor())&&(!e_valid()));
if(as)
{
if(solutie()) afis();
else {k++; init();}
}
else k--;
}
}
int main()
{
ifstream f ("flip.in");
f>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) f>>a[i][j];
back();
g<<smax;
}