Pagini recente » Cod sursa (job #95569) | Cod sursa (job #292479) | Cod sursa (job #184842) | Cod sursa (job #1749187) | Cod sursa (job #1844459)
#include <fstream>
#define nmax 17
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int a[nmax][nmax],n,m;
int x[nmax*2];
int sum[nmax*2];
int s;
void read()
{ int i,j;
fin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{fin>>a[i][j];
s+=a[i][j];
}
}
int suma(int k)
{ int sum=0;
if(x[k]>0)
for(int i=1;i<=m;i++)
sum+=a[x[k]][i];
else
{int p=-x[k];
for(int i=1;i<=n;i++)
sum+=a[i][p];
}
return sum;
}
void schimb(int k)
{ int j;
if(x[k]>0)
for(j=1;j<=m;j++)
a[x[k]][j]=-a[x[k]][j];
else
{int p=-x[k];
for(j=1;j<=n;j++)
a[j][p]=-a[j][p];
}
}
int sumi()
{int i,j;
int s=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
s+=a[i][j];
return s;
}
void Back(int k)
{ int i;
for(i=x[k-1]+1;i<=n;i++)
if(i!=0)
{ x[k]=i;
int su=suma(k);
if(su<0)
{schimb(k);
sum[k]=sumi();
if(sum[k]>s) s=sum[k];
}
if(x[k]<n) Back(k+1);
if(su<0) schimb(k);
}
}
int main()
{ read();
x[0]=-m-1;
Back(1);
fout<<s<<endl;
return 0;
}