Pagini recente » Cod sursa (job #3211275) | Cod sursa (job #1965595) | Cod sursa (job #22224) | Cod sursa (job #1321824) | Cod sursa (job #1844502)
#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 s, l[nmax];
int sum[nmax*2];
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];
l[i]+=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];
l[x[k]]=-l[x[k]];
}
else
{int p=-x[k];
for(j=1;j<=n;j++)
{a[j][p]=-a[j][p];
l[j]+=2*a[j][p];}
}
}
int sal()
{ int s=0;
for(int i=1;i<=n;i++)
s+=l[i];
return s;
}
void Back(int k)
{ int i;
for(i=x[k-1]+1;i<=n;i++)
if(i!=0)
{ x[k]=i;
schimb(k);
sum[k]=sal();
if(s<sum[k]) s=sum[k];
if(x[k]<n) Back(k+1);
schimb(k);
}
}
int main()
{ read();
x[0]=-m-1;
Back(1);
fout<<s<<endl;
return 0;
}