Pagini recente » Cod sursa (job #1570418) | Cod sursa (job #161912) | Cod sursa (job #2211071) | Cod sursa (job #1609002) | Cod sursa (job #3204118)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("flip.in");
ofstream out ("flip.out");
const int NMAX=20;
int n,m;
int a[NMAX][NMAX],aux[NMAX][NMAX];
int v[NMAX];
int maxi=INT_MIN;
int solve(int poz)
{
/*if(cnt==5)
{
out<<poz<<'\n';
for(int i=1; i<=n; i++,out<<'\n')
for(int j=1; j<=m; j++)
out<<a[i][j]<<" ";
}*/
int s=0;
for(int i=1; i<=poz; i++)
{
for(int j=1; j<=n; j++)
{
a[j][v[i]]*=-1;
}
}
for(int i=1; i<=n; i++)
{
int sum=0;
for(int j=1; j<=m; j++)
{
sum+=a[i][j];
}
if(sum<0)
{
for(int j=1; j<=m; j++)
a[i][j]*=-1;
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
s+=a[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
a[i][j]=aux[i][j];
return s;
}
bool ok(int i)
{
return i>=1 && i<=m;
}
void bkt(int poz)
{
for(int i=v[poz-1]+1; i<=m; i++)
{
v[poz]=i;
if(ok(poz))
{
maxi=max(maxi,solve(poz));
if(ok(poz+1))
bkt(poz+1);
}
}
}
int main()
{
in>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
in>>a[i][j];
aux[i][j]=a[i][j];
}
bkt(1);
out<<maxi;
return 0;
}