Cod sursa(job #3271025)

Utilizator AndrulianDin Iulian Andrulian Data 25 ianuarie 2025 04:33:38
Problema Jocul Flip Scor 100
Compilator java Status done
Runda Arhiva de probleme Marime 2.38 kb
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;
    }
}