Submission #1780536

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    int h, w;
    cin >> h >> w;
    
    vector<string> original_board(h);
    repeat(i, h) cin >> original_board[i];
    
    vector<vector<int>> board(h - 1, vector<int> (w - 1, -1));
    
    repeat(i, h - 1) {
        repeat(j, w - 1) {
            int cnt = 0;
            if (original_board[i][j]     == '#') ++cnt;
            if (original_board[i+1][j]   == '#') ++cnt;
            if (original_board[i][j+1]   == '#') ++cnt;
            if (original_board[i+1][j+1] == '#') ++cnt;
            if (cnt % 2 == 1) board[i][j] = 0;
        }
    }
    
    repeat(i, h - 1) {
        repeat(j, w - 1) {
            if (i == 0 && board[i][j] != 0) {
                board[i][j] = 1;
            }
            else if (board[i][j] != 0) {
                board[i][j] = board[i-1][j] + 1;
            }
        }
    }

      
    auto show_stack = [](stack<pair<int, int>> st) -> void {
        if (st.empty()) {cout << "st is empty()\n"; return;}
        while (!st.empty()) {
            cout << st.top().first << ",[" << st.top().second << "]\n";
            st.pop();
        }
    };
    
    auto maximum_rectangle = [&show_stack](vector<int> v) {
        v.push_back(0);
        int n = v.size();
        lint max_size = 0;
        stack<pair<int, int>> st;
        
        vector<pair<int, int>> ret;
        
        repeat(i, n) {
            if (!st.empty()) {
                if (st.top().first < v[i]) {
                    st.push( {v[i], i} );
                }
                else if (st.top().first > v[i]) {
                    while (!st.empty() && st.top().first > v[i]) {
                        int height = st.top().first;
                        int pos = st.top().second;
                        st.pop();
                        lint s = height * (i - pos);
                        
                        if (s > max_size) {
                            max_size = s;
                            ret.clear();
                            ret.push_back( {height, i - pos} );
                        }
                        else if (s == max_size) {
                            ret.push_back( {height, i - pos} );
                        }
                        
                        if (!st.empty() && st.top().first < v[i]) {
                            st.push( {v[i], pos} );
                        }
                    }
                }
            }
            else {
                st.push( {v[i], i} );
            }
        }
        return ret;
    };
    
    lint ans = 0;
    vector<pair<int, int>> rects;
    repeat(i, h - 1) {
        auto v = maximum_rectangle(board[i]);
        rects.insert(rects.end(), v.begin(), v.end());
    }
    
    for(auto rect: rects) {
        ans = max(ans, (lint)(rect.first + 1) * (rect.second + 1));
    }
    cout << ans << endl;
}

Submission Info

Judge Result