Cod sursa(job #2972234)

Utilizator peteanvPetean Vlad peteanv Data 28 ianuarie 2023 21:38:17
Problema Jocul Flip Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 1.6 kb
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;
        }
    }
}