Pagini recente » Cod sursa (job #160742) | Cod sursa (job #1332038) | Cod sursa (job #728031) | Cod sursa (job #1608697) | Cod sursa (job #2166725)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int t[17][17];
int n,m,i,j,k;
long long s,smax;
int a[17],b[17];
struct abc{
int s;
int nr;
};
void check(string q, string p)
{
long long s=0;
int aa[17];
int bb[17];
int i,j;
for(i=1;i<=n;i++) aa[i]=a[i];
for(j=1;j<=m;j++) bb[i]=b[i];
for(i=0;i<n;i++)
if(q[i]=='1')
{
aa[i+1]*=-1;
for(j=1;j<=m;j++)
bb[j]-=2*t[i+1][j];
}
for(i=0;i<m;i++)
if(p[i]=='1')
{
bb[i+1]*=-1;
for(j=1;j<=n;j++)
aa[j]-=2*t[j][i+1];
}
for(i=1;i<=n;i++) s+=aa[i];
smax=max(s,smax);
}
void gen2(string s, string x)
{
if(x.length()==m) check(s,x);
else
{
if(b[x.length()+1]>0) gen2(s,x+'0');
else
{
gen2(s,x+'0');
gen2(s,x+'1');
}
}
}
void gen1(string s)
{
if(s.length()==n) gen2(s,"");
else
{
if(a[s.length()+1]>0) gen1(s+'0');
else
{
gen1(s+'0');
gen1(s+'1');
}
}
}
int main(){
fin>>n>>m;
s=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
fin>>t[i][j];
s+=t[i][j];
}
smax=s;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i]+=t[i][j];
for(j=1;j<=m;j++)
for(i=1;i<=n;i++)
b[j]+=t[i][j];
gen1("");
fout<<smax;
return 0;
}