[백준] 11873 - 최대 직사각형 (c++)

https://www.acmicpc.net/problem/11873

 

문제 요약

0또는 1인 격자가 주어진다. 1로만 이루어진 최대 넓이의 직사각형을 구해라.

 

풀이 (N^2)

• 스택

임의로 바닥을 정하면 히스토그램 문제와 같아진다. 

// #include <bits/stdc++.h>
// using namespace std;
// #define ll long long
// #define all(v) v.begin(),v.end()
// #define rall(v) v.rbegin(),v.rend()
// #define mid (st+en>>1)

// int main() {
//     cin.tie(0)->sync_with_stdio(0);
//     while(1) {
//         int n,m;cin>>n>>m;
//         if(n==0)
//             return 0;
//         vector<vector<int>> ar(n,vector<int>(m));
//         for(auto&x:ar)
//             for(auto&y:x)
//                 cin>>y,y=!y;
//         for(auto&x:ar) {
//             for(int i=1;i<m;i++)
//                 x[i]+=x[i-1];
//         }

//         function<int(int,int,int,int)> dc= [&](int x1,int x2,int y1,int y2) -> int {
//             if(x1>x2||y1>y2)
//             return 0;
//             //cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<'\n';
//             for(int i=x1;i<=x2;i++) {
//                 int f=y1==0?0:ar[i][y1-1];
//                 int id = upper_bound(ar[i].begin()+y1,ar[i].begin()+y2+1,f)-ar[i].begin();
//                 if(id!=y2+1) 
//                 return max({dc(x1,i-1,y1,y2),dc(i+1,x2,y1,y2),dc(x1,x2,y1,id-1),dc(x1,x2,id+1,y2)});
//             }
//             //cout<<'\t'<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<'\n';
//             return (x2-x1+1)*(y2-y1+1);
//         };
//         cout<<dc(0,n-1,0,m-1)<<'\n';
//     }
// } //시간초과

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    while(1) {
        int n,m;cin>>n>>m;
        if(n==0)
            return 0;
        vector<vector<int>> ar(n,vector<int>(m+2));
        for(auto&x:ar)
            for(int i=1;i<=m;i++)
                cin>>x[i];

        for(int j=1;j<=m;j++)
            for(int i=1;i<n;i++)
                if(ar[i][j]>0&&ar[i-1][j]>0)
                    ar[i][j]+=ar[i-1][j];
        
        int ans=0;
        for(int i=0;i<n;i++) {
            stack<int> stk;
            stk.push(0);
            for(int j=1;j<=m+1;j++) {
                while(ar[i][stk.top()]>ar[i][j]) {
                    int x=ar[i][stk.top()];
                    stk.pop();
                    ans=max(ans,x*(j-stk.top()-1));
                }
                stk.push(j);
            }
        }
        cout<<ans<<'\n';
    }
}