2019牛客暑期多校训练营（第二场）H.Second Large Rectangle

错因，用单调栈求出所有极大全1子矩阵，在这些矩阵中取第二大；
最后被
3 5
10100
11100
11101
hack了，仔细想了一下，其实忽略了 （w-1）* h和（h-1）* w ;

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e3+5;
const int inf=0x3f3f3f3f;
#define fi first
#define se second
int a[N][N];
char s[N];
int n,m;
struct node
{
    int l,pos,v;
    node(){}
    node(int ll,int pp,int vv)
    {
        l=ll; pos=pp; v=vv;
    }
};
stack<node> sta;
bool cmp(int x,int y)
{
    return x>y;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s+1);
            for(int j=1;j<=m;j++)
            {
                if(s[j]=='1') a[i][j]=1;
                else a[i][j]=0;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                if(a[i][j]&&a[i-1][j])
                    a[i][j]+=a[i-1][j];
        }
        /*
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%d%c",a[i][j],j==m?'
':' ');*/
        int ans[3];
        memset(ans,0,sizeof(ans) );
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                while(!sta.empty()&&sta.top().v>a[i][j])
                {
                    int w=j-sta.top().l,h=sta.top().v;
                    sta.pop();
                    ans[2]=max(ans[2],w*h );
                    sort(ans,ans+3,cmp);
                    ans[1]=max(ans[1],w*(h-1) );
                    ans[2]=max(ans[2],(w-1)*h);
                    sort(ans,ans+3,cmp);
                }
                sta.push(node(sta.empty()?1:(sta.top().pos+1),j,a[i][j] ) );
            }
            while(!sta.empty())
            {
                int w=m+1-sta.top().l,h=sta.top().v;
                sta.pop();
                ans[2]=max(ans[2],w*h );
                sort(ans,ans+3,cmp);
                ans[1]=max(ans[1],w*(h-1) );
                ans[2]=max(ans[2],(w-1)*h);
                sort(ans,ans+3,cmp);
            }
        }
        printf("%d
",ans[1] );
    }
    return 0;
}
/*
3 5
10100
11100
11101
*/