Pagini recente » Cod sursa (job #468122) | Cod sursa (job #2310865) | Cod sursa (job #1092211) | Cod sursa (job #517315) | Cod sursa (job #2972234)
import java.io.*;
import java.util.*;
public class Main{
static int N, M;
static int[][] board;
static int[] rows, cols;
static int maxSum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("flip.in"));
String[] line = br.readLine().split(" ");
N = Integer.parseInt(line[0]);
M = Integer.parseInt(line[1]);
board = new int[N][M];
rows = new int[N];
cols = new int[M];
for (int i = 0; i < N; i++) {
line = br.readLine().split(" ");
for (int j = 0; j < M; j++) {
board[i][j] = Integer.parseInt(line[j]);
rows[i] += board[i][j];
cols[j] += board[i][j];
}
}
br.close();
backtrack(0);
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("flip.out")));
pw.println(maxSum);
pw.close();
}
static void backtrack(int k) {
if (k == N) {
int sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if ((rows[i] < 0) != (cols[j] < 0)) {
sum += board[i][j];
}
}
}
maxSum = Math.max(maxSum, sum);
return;
}
for (int i = 0; i < 2; i++) {
rows[k] *= -1;
cols[k] *= -1;
backtrack(k + 1);
rows[k] *= -1;
cols[k] *= -1;
}
}
}