Pagini recente » Cod sursa (job #2721160) | Cod sursa (job #547358) | Cod sursa (job #3285499) | Cod sursa (job #969973) | Cod sursa (job #1447482)
#include <stdio.h>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <algorithm>
#include <deque>
#define nmax 18
using namespace std;
int n,m,i,j,linp[nmax],linn[nmax],colp[nmax],coln[nmax],t[nmax][nmax],fr[nmax],frr[nmax],sol=0,maxx;
inline void back(int x)
{
int i,j;
for (i=1;i<=n;i++)
if (linp[i]<linn[i] && fr[i]==0) {
swap(linp[i],linn[i]); sol=sol+2*(linp[i]-linn[i]); fr[i]=1;
for (j=1;j<=m;j++) {
if (t[i][j]<0) colp[j]=colp[j]-t[i][j],coln[j]=coln[j]+t[i][j]; else
colp[j]=colp[j]+t[i][j],coln[j]=coln[j]-t[i][j];
}
back(x+1);
swap(linp[i],linn[i]); sol=sol-2*(linn[i]-linp[i]); fr[i]=0;
for (j=1;j<=m;j++) {
if (t[i][j]<0) colp[j]=colp[j]+t[i][j],coln[j]=coln[j]-t[i][j]; else
colp[j]=colp[j]-t[i][j],coln[j]=coln[j]+t[i][j];
}
}
for (i=1;i<=m;i++)
if (colp[i]<coln[i] && frr[i]==0){
swap(colp[i],coln[i]); sol=sol+2*(colp[i]-coln[i]); frr[i]=1;
for (j=1;j<=n;j++) {
if (t[j][i]<0) linp[j]=linp[j]-t[j][i],linn[j]=linn[j]+t[j][i]; else
linp[j]=linp[j]+t[j][i],linn[j]=linn[j]-t[j][i];
}
back(x+1);
swap(colp[i],coln[i]); sol=sol-2*(coln[i]-colp[i]); frr[i]=0;
for (j=1;j<=n;j++) {
if (t[j][i]<0) linp[j]=linp[j]+t[j][i],linn[j]=linn[j]-t[j][i]; else
linp[j]=linp[j]-t[j][i],linn[j]=linn[j]+t[j][i];
}
}
maxx=max(maxx,sol);
}
int main(){
freopen("flip.in","r",stdin);
freopen("flip.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
scanf("%d",&t[i][j]);
sol=sol+t[i][j];
if (t[i][j]<0) linn[i]=linn[i]+t[i][j],coln[j]=coln[j]+t[i][j]; else
linp[i]=linp[i]+t[i][j],colp[j]=colp[j]+t[i][j];
t[i][j]=2*t[i][j];
}
for (i=1;i<=n;i++) linn[i]=abs(linn[i]);
for (i=1;i<=m;i++) coln[i]=abs(coln[i]);
maxx=-1000000; back(1);
printf("%d\n",maxx);
return 0;
}