Pagini recente » Cod sursa (job #70402) | Cod sursa (job #1436527) | Cod sursa (job #2450093) | Cod sursa (job #2701896) | Cod sursa (job #3143221)
#include <fstream>
#include <climits>
using namespace std;
int n, m, a[20][20], sol = INT_MIN;
int subset[20], len;
void flip_line(int line) {
for(int i = 1; i <= m; i++) {
a[line][i] *= -1;
}
}
void solve_subset() {
for(int i = 1; i <= len; i++) {
flip_line(subset[i]);
}
int total = 0;
for(int col = 1; col <= m; col++) {
int sum_col = 0;
for(int lin = 1; lin <= n; lin++) {
sum_col += a[lin][col];
}
total += abs(sum_col);
}
sol = max(sol, total);
// undo:
for(int i = 1; i <= len; i++) {
flip_line(subset[i]);
}
}
void backtrack(int nr) {
// Am terminat de generat o submultime de linii:
if(nr == n + 1) {
solve_subset();
return;
}
// Caz 1: nu il iau pe nr in submultimile pe care le generez next
backtrack(nr + 1);
// Caz 2: Il iau pe nr in submultimile pe care le generez next
subset[++len] = nr;
backtrack(nr + 1);
--len; // undo
}
int main() {
ifstream fin("flip.in");
ofstream fout("flip.out");
fin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
fin >> a[i][j];
}
}
backtrack(1);
fout << sol << "\n";
return 0;
}