  PKU 3494
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define maxn 2000+5
int a[maxn][maxn];
int m,n;
int solve()
{
int ans=0;
int h[maxn],l[maxn],r[maxn];
/*
l[i]：第i列所在的极大化子矩阵的最左端
r[i]：第i列所在的极大化子矩阵的最右端
left：当前行所在的极大化子矩阵的最左端
right：当前行所在的极大化子矩阵的最右端
*/
int left,right;
for(int j=0;j<n;j++)
{
h[j]=0; l[j]=0; r[j]=n-1;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j]==1)
h[j]++;
else h[j]=0;
}
left=0;
for(int j=0;j<n;j++)
{
if(h[j]) //该处是1
l[j]=max(l[j],left);
else //该处为0（“障碍”）
{
left=j+1;//所以能达到的最左端为j+1
l[j]=0; //l[j]置为0是为了在计算第i+1行
}
}
right=n-1;
for(int j=n-1;j>=0;j--)
{
if(h[j])
r[j]=min(r[j],right);
else
{
right=j-1;
r[j]=n-1;
}
}
for(int j=0;j<n;j++)
if(h[j])
ans=max(h[j]*(r[j]-l[j]+1),ans);
}
return ans;
}
int main()
{
char s[4001];
while(scanf("%d%d",&m,&n)!=EOF)
{
getchar();
for(int i=0;i<m;i++)
{
gets(s);
for(int j=0;j<n;j++)
//scanf("%d",&a[i][j]);
a[i][j]=s[j*2]-'0';
}
printf("%d\n",solve());
}
}
|