Pagini recente » Cod sursa (job #1696388) | Cod sursa (job #1085774) | Cod sursa (job #2378331) | Cod sursa (job #1349541) | Cod sursa (job #1263979)
#include<stdio.h>
int n,m,mat[20][20],sgn[20],max_sum=-99999999;
int get_sum()
{
int ret=0;
for(int i=0;i<n;++i)
{
int s=0;
for(int j=0;j<m;++j)s+=sgn[j]*mat[i][j];
if(s<0)s*=-1;
ret+=s;
}
return ret;
}
void backtrack_sgn(int poz)
{
if(poz<m)
{
sgn[poz]=1;
backtrack_sgn(poz+1);
sgn[poz]=-1;
backtrack_sgn(poz+1);
}
else
{
int current_sum = get_sum();
if(current_sum>max_sum)max_sum=current_sum;
}
}
int main()
{
freopen("flip.in","r",stdin);
freopen("flip.out","w",stdout);
scanf("%d%d",&n,&m);
if(n>=m)
{
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)scanf("%d",&mat[i][j]);
}
else
{
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)scanf("%d",&mat[j][i]);
int aux = n;
n = m;
m = aux;
}
for(int k=0;k<(1<<m);++k)
backtrack_sgn(0);
printf("%d\n",max_sum);
return 0;
}