Pagini recente » Cod sursa (job #617892) | Cod sursa (job #976248) | Cod sursa (job #1141886) | Cod sursa (job #410302) | Cod sursa (job #575741)
Cod sursa(job #575741)
#include<cstdio>
using namespace std;
int n,m,s,a[17][17],inter[17][17],S[50];
void Solve(int k)
{int i,j,r=0,S1,S2;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
inter[i][j]=a[i][j];
for(j=1;j<=k;j++)
for(i=1;i<=n;i++)
inter[i][S[j]] = -inter[i][S[j]];
for(i=1;i<=n;i++)
{
S1=0;
S2=0;
for(j=1;j<=m;j++)
{
S1=S1+inter[i][j];
S2=S2-inter[i][j];
}
if(S1>S2)
r+=S1;
else r+=S2;
}
if(r>s)
s=r;
}
void Backtrack (int k)
{
Solve(k-1);
for(int i=1+S[k-1];i<=m;i++)
{
S[k]=i;
Backtrack(k+1);
}
}
int main()
{
int i,j;
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",&a[i][j]);
fclose(stdin);
Backtrack(1);
printf("%d",s);
fclose(stdout);
return 0;
}