Pagini recente » Cod sursa (job #1514481) | Cod sursa (job #3177464) | Cod sursa (job #863432) | Cod sursa (job #1021633) | Cod sursa (job #2460418)
#include <bits/stdc++.h>
#define NM 20
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int n,m,sMax,sMaxim,sl[NM],sc[NM],a[NM][NM];
bool viz[NM],st[NM];
void Read();
void Solve();
void BKT1(int);
void BKT2(int);
void SolBKT1();
void SolBKT2();
int main()
{ Read();
Solve();
}
void Read()
{ f>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
f>>a[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
sl[i]+=a[i][j];
for(int j=1; j<=m; j++)
for(int i=1; i<=n; i++)
sc[j]+=a[i][j];
}
void SolBKT1()
{ int sum=0;
for(int i=1; i<=m; i++)
sum+=(st[i] ? -sc[i] : sc[i]);
sMax=max(sMax,sum);
}
void BKT1(int vf)
{ if(vf==m+1)
SolBKT1();
else
for(int i=0; i<=1; i++)
{ st[vf]=i;
BKT1(vf+1);
}
}
void SolBKT2()
{ int sum=sMax;
for(int i=1; i<=n; i++)
if(st[i])
sum+=-2*sl[i];
sMaxim=max(sMaxim,sum);
}
void BKT2(int vf)
{ if(vf==n+1)
SolBKT2();
else
for(int i=0; i<=1; i++)
{ st[vf]=i;
BKT2(vf+1);
}
}
void Solve()
{ BKT1(1);
for(int i=1; i<=n; i++)
st[i]=false;
BKT2(1);
g<<sMaxim;
}