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 |
|
|
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 |