// Runtime: 1 ms, faster than 40.06% of Java online submissions for Score After Flipping Matrix.
class Solution {
    int[][] a;
    int m;
    int n;
    public int matrixScore(int[][] A) {
        a = A;
        m = a.length;
        n = a[0].length;


        for (int r = 0; r < m; r++)
            if (a[r][0] == 0) flipRow(r);

        int max = opt(0);

        for (int r = 0; r < m; r++)
            flipRow(r);

        max = Math.max(max, opt(0));
        return max;
    }

    private int opt(int c){
        if (c == n) return score();

        int ones = 0;
        for (int r = 0; r < m; r++)
            if (a[r][c] == 1) ones++;

        int max = 0;
        if (ones >= m/2){
            max = Math.max(max, opt(c+1));
        }
        if (ones <= m/2) {
            flipColumn(c);
            max = Math.max(max, opt(c+1));
            flipColumn(c);
        }
        return max;
    }

    private int score() {
        int sum = 0;

        for (int r = 0; r < m; r++) {
            int num = 0;
            int p = 1;
            for (int c = n-1; c >= 0; c--){
                if (a[r][c] == 1) num += p;
                p <<= 1;
            }
            sum += num;
        }

        return sum;
    }

    private void flipColumn(int c) {
        for (int r = 0; r < m; r++) a[r][c] = 1 - a[r][c];
    }

    private void flipRow(int r) {
        for (int c = 0; c < n; c++) a[r][c] = 1 - a[r][c];
    }
}