logo AlgoBeat OnlineJudge
登录 注册

#10022. [NFLS 信息特长生 2026 T2] 最大 1 矩阵 / [CF375B] Maximum Submatrix 2

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: joe_zxq 彩笔

题目描述

给定一个 列的 0-1 矩阵。你可以对矩阵的行进行任意次重排(即任意交换两行的位置),但不能改变列的顺序。请问,在最优的行排列下,矩阵中最大的全 子矩阵(即所有元素均为 的矩形)的面积最大是多少?

输入格式

第一行两个整数 ,分别表示矩阵的行数和列数。 接下来 行,每行 个整数,表示矩阵中的元素(每个数为 )。

输出格式

一个整数,表示最大可能的全 子矩阵的面积。

样例

样例输入 #1

4 5
10101
11011
11111
10010

样例输出 #1

6

数据范围与提示

样例解释

一种可行的行重排方式为:

1 1 1 1 1
1 1 0 1 1
1 0 1 0 1
1 0 0 1 0

此时,选取第 列到第 列、第 行到第 行的子矩阵(即 )面积为 。可以证明这是最优的。

数据范围

· · 矩阵元素均为