Pagini recente » Cod sursa (job #532430) | Cod sursa (job #2532440) | Cod sursa (job #1710392) | Monitorul de evaluare | Cod sursa (job #586084)
Cod sursa(job #586084)
#include <iostream>
#include <cstdio>
using namespace std;
const int NMAX = 16;
const int INF = -1000002;
int n,m,sol=INF;
int matrix[NMAX][NMAX];
int sumPoz[NMAX], sumNeg[NMAX];
inline void debug_matrix(){
for(int i=0;i<n;++i){
for(int j=0;j<m;++j)
cerr<<matrix[i][j]<<' ';
cerr<<'\n';
}
cerr<<'\n';
}
void read_problem(){
freopen("flip.in","r",stdin);
freopen("flip.out","w",stdout);
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<n;++i)
for(j=0;j<m;++j){
scanf("%d",&matrix[i][j]);
if (matrix[i][j]>0)
sumPoz[i]+=matrix[i][j];
else
sumNeg[i]-=matrix[i][j];
}
}
int sum(){
int s = 0;
for(int i=0;i<n;++i)
s+=max(sumPoz[i]-sumNeg[i],sumNeg[i]-sumPoz[i]);
return s;
}
void flip_column(int k){
for(int i=0; i<n; ++i){
sumPoz[i] -= matrix[i][k];
sumNeg[i] += matrix[i][k];
matrix[i][k] = -matrix[i][k];
}
}
void back(int k){
sol = max(sol,sum());
if (k == m)
return;
for(int i=k; i<n; ++i){
back(k+1);
flip_column(i);
back(k+1);
}
}
int main()
{
read_problem();
back(0);
printf("%d\n",sol);
return 0;
}