Pagini recente » Cod sursa (job #1449349) | Cod sursa (job #1506705) | Cod sursa (job #641647) | Cod sursa (job #208641) | Cod sursa (job #2832606)
#include <fstream>
int n, m;
int arr[16][16];
int max = INT32_MIN;
std::ifstream in("flip.in");
std::ofstream out("flip.out");
bool com[2][16];
void solve(int sum, int k) {
if (k > 2) return;
if (sum > max) max = sum;
for (int i=0; i<n; i++) {
if (com[0][i]) continue;
int s = 0;
for (int j=0; j<m; j++)
s += arr[i][j];
if (s < 0) {
if (sum - 2*s < max) k++;
for (int j=0; j<m; j++)
arr[i][j] *= -1;
com[0][i] = 1;
solve(sum - 2*s, k);
com[0][i] = 0;
for (int j=0; j<m; j++)
arr[i][j] *= -1;
k--;
}
}
for (int i=0; i<m; i++) {
if (com[1][i]) continue;
int s = 0;
for (int j=0; j<n; j++)
s += arr[j][i];
if (s < 0) {
if (sum - 2*s < max) k++;
for (int j=0; j<n; j++)
arr[j][i] *= -1;
com[1][i] = 1;
solve(sum - 2*s, k);
com[1][i] = 0;
for (int j=0; j<n; j++)
arr[j][i] *= -1;
k--;
}
}
}
int main() {
in >> n >> m;
int sum = 0;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
in >> arr[i][j],
sum += arr[i][j];
solve(sum,0);
out << max;
}