对于测试点 $1, 2, 3$，可以直接枚举行的范围，再全排列检查有多少个是符合条件的。

本题属于优化暴力类型，则我们需要一个高级数据结构优化全排列的过程，这个过程其实是在查询有多少个区间包含当前区间。

只需要用树状数组和离线查询就可以了，具体看代码。

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr size_t N = 3005;
int n, m;
char grid[N][N];
array<int, 2> arr[N * N];
int tot;
int tree[N];
void add(int i)
{
    while (i <= m)
    {
        tree[i]++;
        i += i & -i;
    }
}
int query(int i)
{
    int res = 0;
    while (i > 0)
    {
        res += tree[i];
        i &= i - 1;
    }
    return res;
}
int query(int l, int r)
{
    return query(r) - query(l - 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> grid[j][i];
        }
    }
    swap(n, m);
    for (int i = 1; i <= n; i++)
    {
        for (int l = 1, r = 1; l <= m; l = ++r)
        {
            if (grid[i][r] == '1')
            {
                continue;
            }
            while (r < m && grid[i][l] == grid[i][r + 1])
            {
                r++;
            }
            arr[++tot][0] = l;
            arr[tot][1] = r;
        }
    }
    sort(arr + 1, arr + tot + 1);
    int p = 1;
    int res = 0;
    for (int i = 1; i <= m; i++)
    {
        while (p <= tot && arr[p][0] <= i)
        {
            add(arr[p++][1]);
        }
        for (int j = i; j <= m; j++)
        {
            res = max(res, (j - i + 1) * query(j, m));
        }
    }
    cout << res << '\n';
    return 0;
}

一个矩形用了 $h$ 列、高 $H$ 行，它只要求"这 $h$ 列在这 $H$ 行里全是空的"，具体是哪 $h$ 列无所谓。所以只要知道

高度至少为 $H$ 的列一共有几列

就够了。

列可以任意交换，等价于说：任意一列子集都能被聚到一起变成连续的若干列。所以「选一个不覆盖障碍物的矩形」等价于

选一个行区间 $[r_1,r_2]$，把所有在这个行区间内全是 0 的列都选上（多选不亏），面积 $=(r_2-r_1+1)\times(\text{这样的列数})$。

于是枚举矩形的下边 $r_2$，同时维护每一列上"以 $r_2$ 结尾的连续 0 的个数" $h_j$。对某个高度 $H$，能用的列正是满足 $h_j\ge H$ 的那些；把 $h$ 从大到小排序后，第 $i$ 大的 $h$ 乘上 $i$，就是"高度至少为这个 $h$ 的列有 $i$ 列"时能得到的面积，对所有 $i$ 取最大值即可。