Pagini recente » Cod sursa (job #494015) | Cod sursa (job #2298295) | Cod sursa (job #2999514) | Cod sursa (job #40152) | Cod sursa (job #2856235)
#include <bits/stdc++.h>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int n,m;
int mat[18][18];
bool lin_flip[18],col_flip[18];
int suminit,summax;
void read() {
f >> n >> m;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
f >> mat[i][j];
suminit += mat[i][j];
mat[n+1][j] += mat[i][j];
mat[i][m+1] += mat[i][j];
}
}
}
void line(int lin) {
mat[lin][m+1] = -mat[lin][m+1];
for (int j=1;j<=m;j++) {
mat[lin][j] = -mat[lin][j];
mat[n+1][j] += 2*mat[lin][j];
}
}
void column(int col) {
mat[n+1][col] = -mat[n+1][col];
for (int i=1;i<=n;i++) {
mat[i][col] = -mat[i][col];
mat[i][m+1] += 2*mat[i][col];
}
}
void bkt(int sum) {
summax = max(summax,sum);
for (int i=1;i<=n;i++) {
if (mat[i][m+1]<0 && !lin_flip[i]) {
line(i);
lin_flip[i]=1;
bkt(sum+2*mat[i][m+1]);
line(i);
lin_flip[i]=0;
}
}
for (int j=1;j<=m;j++) {
if (mat[n+1][j]<0 && !col_flip[j]) {
column(j);
col_flip[j]=1;
bkt(sum+2*mat[n+1][j]);
column(j);
col_flip[j]=0;
}
}
}
int main()
{
read();
bkt(suminit);
g << summax;
return 0;
}