51nod 1158 全是1的最大子矩阵(单调栈 ,o(n*m))

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[510][510]; 
int l[510],r[510];
int main(){
    ios::sync_with_stdio(false);
    int m,n;
    cin >> m >> n;
    for(int i = 1;i <= m; ++i){
        for(int j = 1;j <= n; ++j){
            cin >> a[i][j];
            if(a[i][j] == 1)  a[i][j] += a[i][j-1];
        }
    }
    int ans = 0;
    for(int i = 1;i <= n; ++i){
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        stack<int> s; 
        s.push(1);
        a[0][i] = a[m+1][i] = -1;
        for(int j = 2;j <= m+1; ++j){
            while(s.size() and a[j][i] < a[s.top()][i]){
                r[s.top()] = j;
                s.pop();
            }
            s.push(j);
        }
        while(s.size()) s.pop();
        s.push(m);
        for(int j = m-1;j >= 0; --j){
            while(s.size() and a[j][i] < a[s.top()][i]){
                l[s.top()] = j;
                s.pop();
            }
            s.push(j);
        }
        for(int j = 1;j <= m; ++j){
            ans = max(ans, (r[j]-l[j]-1)*a[j][i]);
        }
    }
    cout << ans << endl;
    return 0;
}