Pagini recente » Cod sursa (job #103838) | Cod sursa (job #2551711) | Cod sursa (job #2941038) | Cod sursa (job #1796594) | Cod sursa (job #1462590)
#include <fstream>
#include <limits>
#define int64 long long
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
int a[20][20],n,m,l[20],c[20],mx;
void line(int x)
{
for(int i=1;i<=m;i++)
{
a[x][0]-=a[x][i];
a[0][i]-=a[x][i];
a[x][i]=-a[x][i];
a[x][0]+=a[x][i];
a[0][i]+=a[x][i];
}
}
void col(int x)
{
for(int i=1;i<=n;i++)
{
a[0][x]-=a[i][x];
a[i][0]-=a[i][x];
a[i][x]=-a[i][x];
a[0][x]+=a[i][x];
a[i][0]+=a[i][x];
}
}
int64 getsum()
{
int sum=0;
for(int i=1;i<=n;i++)
sum+=a[i][0];
return sum;
}
void back(int lastl)
{
for(int i=1;i<=m;i++)
if(a[0][i]<0)
col(i);
mx=max(mx,getsum());
for(int i=lastl+1;i<=n;i++)
if(l[i]==0){
l[i]++;
line(i);
back(i);
line(i);
l[i]--;
}
}
int main()
{
in>>n>>m;
mx=numeric_limits<int64>::min();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
in>>a[i][j];
a[i][0]+=a[i][j];
a[0][j]+=a[i][j];
}
back(0);
out<<mx<<'\n';
return 0;
}