Pagini recente » Cod sursa (job #2736643) | Cod sursa (job #2035752) | Cod sursa (job #917840) | Cod sursa (job #1052479) | Cod sursa (job #1978845)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n, m;
int s, ss;
int a[18][18];
int scol[18];
bool l[18], c[18];
void flipl(int l)
{
int i;
for(i=1; i<=m; i++)
{
ss-=2*a[l][i];
scol[i]-=2*a[l][i];
if(scol[i]>0)
c[i]=1;
else
c[i]=0;
a[l][i]*=(-1);
}
}
void flipc(int c)
{
int i;
for(i=1; i<=n; i++)
{
ss-=2*a[i][c];
a[i][c]*=(-1);
}
}
void bkc(int p)
{
int i;
for(i=1; i<=m; i++)
if(!c[i])
{
c[i]=1;
flipc(i);
if(ss>s)
s=ss;
if(p<n)
bkc(p+1);
flipc(i);
c[i]=0;
}
}
void bk(int p)
{
int i;
for(i=1; i<=n; i++)
if(!l[i])
{
l[i]=1;
flipl(i);
if(ss>s)
s=ss;
bkc(1);
if(p<n)
bk(p+1);
flipl(i);
l[i]=0;
}
}
void calibreaza_coloane()
{
int i;
for(i=1; i<=m; i++)
if(scol[i]>0)
c[i]=1;
}
int main()
{
fin>>n>>m;
int i, j;
for(i=1; i<=n; i++)
{
ss=0;
for(j=1; j<=m; j++)
fin>>a[i][j], ss+=a[i][j], scol[j]+=a[i][j];
if(ss>0)
l[i]=1;
s+=ss;
}
ss=s;
calibreaza_coloane();
bk(1);
fout<<s<<'\n';
return 0;
}