Pagini recente » Cod sursa (job #1594108) | Cod sursa (job #2746711) | Cod sursa (job #2690636) | Cod sursa (job #712590) | Cod sursa (job #3263056)
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
#define INF 1e18
int a[20][20];
long long smax = -INF;
int subm[20];
bool uz1[20], uz2[20];
long long sum(int n, int m) {
long long s = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int semn = 1;
if (uz1[i]) {
semn *= -1;
}
if (uz2[j]) {
semn *= -1;
}
s += semn * a[i][j];
}
}
return s;
}
void back(int k, int n, int m) {
for (int i = 1; i <= n; ++i) {
if (!uz1[i]) {
uz1[i] = 1;
int s = sum(n, m);
if (s > smax) {
smax = s;
}
if (k < n) {
back(k + 1, n, m);
}
uz1[i] = 0;
}
}
for (int i = 1; i <= m; ++i) {
if (!uz2[i]) {
uz2[i] = 1;
int s = sum(n, m);
if (s > smax) {
smax = s;
}
if (k < n) {
back(k + 1, n, m);
}
uz2[i] = 0;
}
}
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
fin >> a[i][j];
}
}
back(1, n, m);
fout << smax;
return 0;
}