题目

Description

Given an N * M matrix with each entry equal to 0 or 1. We can find some rectangles in the matrix whose entries are all 1, and we define the maximum area of such rectangle as this matrix’s goodness.

We can swap any two columns any times, and we are to make the goodness of the matrix as large as possible.

Input

There are several test cases in the input. The first line of each test case contains two integers N and M (1 ≤ N,M ≤ 1000). Then N lines follow, each contains M numbers (0 or 1), indicating the N * M matrix

Output

Output one line for each test case, indicating the maximum possible goodness.

Sample Input

3 4
1011
1001
0001
3 4
1010
1001
0001

Sample Output

4
2

翻译

背景

在一个由 0 和 1 填充的 N * M 的矩形,我们可以从其中找到一些矩形矩阵的为 1 的方格,将其能达到的最大面积称为最大面积
我们可以任意交换两列方格,从而使能够达到的面积更大

输入

输入包括多组数据
每组第一行是两个整数 N 和 M ( 1<=N,M<=1000 )
接下来 N 行每行有 M 个数,构成 N * M 的矩阵

输出

在一行中输出最大的矩形

题解

可以看出是>最大矩形问题<的修改版

由于每一列都可以移动,我们在每次计算以第 i 行为低的矩阵时,应该尽可能把图形移动成能够获得更大面积矩形的情况
稍微画下可以发现,有序排列每个宽度为 1 的小矩形是最优解
因此可以先对以 i 为底的矩形的高排序,再计算最大矩形

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn = 1005;

bool Map[maxn][maxn];

int H[maxn][maxn];

int Left[maxn];
int Right[maxn];

int MaxMatrix(bool Matrix[maxn][maxn],int n,int m,bool target) {
    memset(H,0,sizeof(H));
    memset(Left,0,sizeof(Left));
    memset(Right,0,sizeof(Right));

    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++) {
            if(Matrix[i][j] == target) {
                if(Matrix[i - 1][j])
                    H[i][j] = H[i - 1][j] + 1;
                else
                    H[i][j] = 1;
            }
        }

    int Max = 0;
    for(int i = 1;i <= n;i++) {
        sort(H[i] + 1,H[i] + 1 + m);

        for(int j = 1;j <= m;j++) {
            //if(Matrix[i][j] == target) {
                int t = j;
                while(t > 1 && H[i][j] <= H[i][t - 1])
                    t = Left[t - 1];
                Left[j] = t;
            //}
        }
        for(int j = m;j >= 1;j--) {
            //if(Matrix[i][j] == target) {
                int t = j;
                while(t < m && H[i][j] <= H[i][t + 1])
                    t = Right[t + 1];
                Right[j] = t;
            //}
        }

        for(int j = 1;j <= m;j++) {
            //if(Matrix[i][j] == target) {
                int S = H[i][j] * (Right[j] - Left[j] + 1);
                Max = max(Max,S);
            //}
        }

    }

    return Max;
}

bool  Do() {
    int n,m;
    if(scanf("%d%d",&n,&m) == EOF)
        return false;

    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++) {
            char t;
            scanf("\n%c",&t);
            Map[i][j] = (t == '1');
        }

    int ans = MaxMatrix(Map,n,m,true);

    printf("%d\n",ans);
    return true;
}

int main() {
    while(Do());
    return 0;
}