题意简述

给定一个只包含 的矩阵，如果可以无数次交换任意两行，求一个只包含 的子矩阵且满足面积最大，最大面积是多少？

思路分析

考虑到矩形的边一定是横平竖直的，所以先尝试确定下矩形的一边。图 1 中，如使 为矩形的一边，标定为 ，来分析怎样计算交换后的最大矩形面积。

首先，在 左侧的数字中只有最右侧的连续一段的 才有可能记成以 为边的矩形的组成部分。这部分是我们计算要使用的，标定为 ，可以考虑预处理出 表示坐标 左侧连续 的个数。

接下来，我们考虑 无数次交换任意两行 这个操作，如果每两行都可以无限交换，那么这个矩阵可以随意改变行的先后顺序，也就是按照一定顺序对行排序。

想到这点后，我们思考如何排序有利于矩形面积的计算。显然，当对同一列的 从小到大排序时，对于每个第 列第 行的 值，它对后面更大的 值的位置有贡献，这里 一定在 后面，因而 ，所以 一定能和 形成矩形，这个矩形中 就是矩形的宽， 就是矩形的长。很明显， 越大矩形的长越大，矩形的宽又不 变，矩形的面积就最大，于是 最优值取 。

总结上一段，我们对列 的 值从小到大排序，依次遍历行 ，矩形最大面积不断和 取最大值，即可得到答案。

上图图 1 处理后形成下图：

注意：下图中 本应不改变，但为了识别不同的行在什么位置，我手动将它改变，上文中的 和 与下图中 无关。

图 2 中考虑第 行时，最大矩形面积为 。

图 3 中考虑第 行时，最大矩形面积为 。

图 4 中考虑第 行时，最大矩形面积为 。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int NR = 5010;
char a[NR][NR];
int c[NR][NR];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++)
	{
		scanf("%s", a[i] + 1);
	}
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= m; j ++)
		{
			if (a[i][j] == '1') c[j][i] = c[j - 1][i] + 1;
			else c[j][i] = 0;
		}
	}
	int ans = 0;
	for (int j = 1; j <= m; j ++)
	{
		sort(c[j] + 1, c[j] + n + 1);
		for (int i = 1; i <= n; i ++)
		{
			ans = max(ans, c[j][i] * (n - i + 1));
		}
	}
	cout << ans << endl;
	return 0;
}