Submission #1792657


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) {
    lint 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));
    }
    
    ans = max(ans, h);
    ans = max(ans, w);
    cout << ans << endl;
}

Submission Info

Submission Time
Task F - Flip and Rectangles
User maphylageo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3666 Byte
Status WA
Exec Time 304 ms
Memory 20096 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 31
WA × 9
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt AC 3 ms 512 KB
10.txt AC 202 ms 20096 KB
11.txt WA 93 ms 12544 KB
12.txt AC 172 ms 19968 KB
13.txt AC 172 ms 20096 KB
14.txt WA 172 ms 19968 KB
15.txt WA 173 ms 20096 KB
16.txt WA 173 ms 20096 KB
17.txt WA 173 ms 20096 KB
18.txt AC 216 ms 19968 KB
19.txt AC 184 ms 20096 KB
2.txt AC 2 ms 256 KB
20.txt AC 187 ms 19968 KB
21.txt WA 187 ms 20096 KB
22.txt WA 187 ms 20096 KB
23.txt WA 304 ms 20096 KB
24.txt AC 173 ms 20096 KB
25.txt AC 173 ms 20096 KB
26.txt AC 219 ms 20096 KB
27.txt AC 206 ms 20096 KB
28.txt AC 215 ms 20096 KB
29.txt AC 173 ms 20096 KB
3.txt AC 248 ms 20096 KB
30.txt AC 180 ms 20096 KB
31.txt AC 174 ms 20096 KB
32.txt AC 173 ms 20096 KB
33.txt AC 173 ms 20096 KB
34.txt AC 173 ms 20096 KB
4.txt AC 247 ms 20096 KB
5.txt AC 3 ms 512 KB
6.txt AC 2 ms 256 KB
7.txt AC 220 ms 20096 KB
8.txt AC 220 ms 20096 KB
9.txt WA 201 ms 20096 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB