Cod sursa(job #2972229)

Utilizator peteanvPetean Vlad peteanv Data 28 ianuarie 2023 21:34:34
Problema Jocul Flip Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 1.41 kb
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main{
    static int N, M;
    static int[][] arr;
    static int bestSum;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(new File("flip.in"));
        N = sc.nextInt();
        M = sc.nextInt();
        arr = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        sc.close();

        bestSum = Integer.MIN_VALUE;
        backtrack(0, 0, 0);

        PrintWriter pw = new PrintWriter(new File("flip.out"));
        pw.println(bestSum);
        pw.close();
    }

    static void backtrack(int row, int col, int sum) {
        if (row == N) {
            bestSum = Math.max(bestSum, sum);
            return;
        }
        if (col == M) {
            backtrack(row + 1, 0, sum);
            return;
        }

        backtrack(row, col + 1, sum);
        int newSum = sum + flip(row, col) * 2;
        backtrack(row, col + 1, newSum);
    }

    static int flip(int row, int col) {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += arr[i][col] *= -1;
        }
        for (int j = 0; j < M; j++) {
            sum += arr[row][j] *= -1;
        }
        return sum;
    }
}