Given a (n \times m) matrix where each cell contains either 0 (white) or 1 (black), a subrectangle is considered balanced if the number of black cells equals the number of white cells inside it. The task is to find the area (total number of cells) of the largest balanced subrectangle, or 0 if none exists.

Both (n) and (m) are at most 10, which makes it feasible to examine every possible subrectangle explicitly.

Approach

Since the constraints are extreme small, the simplest02-based brute force works well. We can enumerate all pairs of top-left and bottom-right corners and check the balance condition for each subrectangle.

To avoid repeated summation we can precompute a 2D prefix sum array pref where pref[i][j] stores the number of black cells in the submatrix from (1,1) to (i,j). Then the black count in any subrectangle (r1,c1)–(r2,c2) can be retrieved in constant time:

[ \text{blacks} = pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1] ]

A subrectangle is balanced when:

[ \text{blacks} \times 2 = \text{area} = (r2 - r1 + 1) \times (c2 - c1 + 1) ]

We track the maximum area among all balanced subrectangles.

Time complexity is (O(n^2 m^2)).

Example

Input:

4 5
00000
01111
00011
00011

The largest balanced subrectangle has area 16.

Implementation

The code uses 1‑based indexing for the prefix sum to simplify edge handling.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int rows, cols;
    cin >> rows >> cols;
    
    vector<vector<int>> grid(rows + 1, vector<int>(cols + 1, 0));
    vector<vector<int>> pref(rows + 1, vector<int>(cols + 1, 0));
    
    for (int r = 1; r <= rows; ++r) {
        string rowData;
        cin >> rowData;
        for (int c = 1; c <= cols; ++c) {
            grid[r][c] = rowData[c-1] - '0';
            pref[r][c] = grid[r][c] + pref[r-1][c] + pref[r][c-1] - pref[r-1][c-1];
        }
    }
    
    int bestArea = 0;
    
    for (int top = 1; top <= rows; ++top) {
        for (int left = 1; left <= cols; ++left) {
            for (int bottom = top; bottom <= rows; ++bottom) {
                for (int right = left; right <= cols; ++right) {
                    int blackCnt = pref[bottom][right]
                                 - pref[top-1][right]
                                 - pref[bottom][left-1]
                                 + pref[top-1][left-1];
                    int area = (bottom - top + 1) * (right - left + 1);
                    if (blackCnt * 2 == area) {
                        bestArea = max(bestArea, area);
                    }
                }
            }
        }
    }
    
    cout << bestArea << endl;
    return 0;
}

All possible subrectangles are examined. When (n) and (m) stay with in 10, this simple approach runs instantly.