Pagini recente » Cod sursa (job #2419580) | Cod sursa (job #1573187) | Cod sursa (job #2323872) | Cod sursa (job #72420) | Cod sursa (job #3271025)
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] matrix;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new FileReader("flip.in"))) {
PrintWriter pw = new PrintWriter(new FileWriter("flip.out"));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
matrix = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
int maxSum = Integer.MIN_VALUE;
// Iterăm prin toate configurațiile posibile de flip pentru liniile (2^N)
for (int rowMask = 0; rowMask < (1 << N); rowMask++) {
int[][] flippedMatrix = flipRows(rowMask);
maxSum = Math.max(maxSum, optimizeColumns(flippedMatrix));
}
pw.println(maxSum);
pw.close();
} catch (NumberFormatException e) {
e.printStackTrace();
}
}
// Aplicăm flip pe liniile selectate prin rowMask
static int[][] flipRows(int rowMask) {
int[][] newMatrix = new int[N][M];
for (int i = 0; i < N; i++) {
boolean flipRow = (rowMask & (1 << i)) != 0;
for (int j = 0; j < M; j++) {
newMatrix[i][j] = flipRow ? -matrix[i][j] : matrix[i][j];
}
}
return newMatrix;
}
// Optimizăm alegerea coloanelor pentru suma maximă
static int optimizeColumns(int[][] mat) {
int totalSum = 0;
for (int j = 0; j < M; j++) {
int columnSum = 0;
for (int i = 0; i < N; i++) {
columnSum += mat[i][j];
}
// Calculăm suma inversată pentru această coloană
int flippedSum = 0;
for (int i = 0; i < N; i++) {
flippedSum += -mat[i][j];
}
// Alegem varianta care maximizează suma totală
totalSum += Math.max(columnSum, flippedSum);
}
return totalSum;
}
}