Submission #1780723
Source Code Expand
#include <iostream> #include <sstream> #include <cstdio> #include <cstdlib> #include <cmath> #include <ctime> #include <cstring> #include <string> #include <vector> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <numeric> #include <utility> #include <iomanip> #include <algorithm> #include <functional> using namespace std; #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl #define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i) template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) { EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; } int N, M; string S[2100]; int co[2100][2100]; int num[2100][2100]; long long LargestRectangle(vector<long long> height) { stack<long long> st; vector<long long> left(height.size()), right(height.size()); for (int i = 0; i < (int)height.size(); ++i) { while (!st.empty() && height[st.top()] >= height[i]) st.pop(); left[i] = !st.empty() ? st.top() + 1 : 0; st.push(i); } while (!st.empty()) st.pop(); for (int i = (int)height.size() - 1; i >= 0; --i) { while (!st.empty() && height[st.top()] >= height[i]) st.pop(); right[i] = !st.empty() ? st.top() : height.size(); st.push(i); } long long res = 0; for (int i = 0; i < (int)height.size(); ++i) { //res = max(res, height[i] * (right[i] - left[i])); chmax(res, (height[i] + 1) * (right[i] - left[i] + 1)); } return res; } long long solve() { long long res = max(N, M); memset(co, 0, sizeof(co)); for (int i = 0; i < N-1; ++i) { for (int j = 0; j < M-1; ++j) { int siro = 0, kuro = 0; for (int k = 0; k < 2; ++k) for (int l = 0; l < 2; ++l) { if (S[i+k][j+l] == '#') ++kuro; else ++siro; } if (kuro % 2 == 0) co[i][j] = 1; else co[i][j] = 0; } } memset(num, 0, sizeof(num)); for (int i = 0; i < N-1; ++i) { int tmp = 0; for (int j = M-2; j >= 0; --j) { if (co[i][j] == 1) { ++tmp; } else { tmp = 0; } num[i][j] = tmp; //cout << i << ", " << j << ": " << co[i][j] << ", " << tmp << endl; } } for (int j = 0; j < M-1; ++j) { vector<long long> vec; for (int i = 0; i < N-1; ++i) vec.push_back(num[i][j]); chmax(res, LargestRectangle(vec)); } return res; } int main() { while (cin >> N >> M) { for (int i = 0; i < N; ++i) cin >> S[i]; cout << solve() << endl; } }
Submission Info
Submission Time | |
---|---|
Task | F - Flip and Rectangles |
User | drken |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 3522 Byte |
Status | AC |
Exec Time | 299 ms |
Memory | 38912 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 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 | 11 ms | 34816 KB |
10.txt | AC | 273 ms | 38912 KB |
11.txt | AC | 131 ms | 38784 KB |
12.txt | AC | 236 ms | 38912 KB |
13.txt | AC | 237 ms | 38912 KB |
14.txt | AC | 237 ms | 38912 KB |
15.txt | AC | 240 ms | 38912 KB |
16.txt | AC | 239 ms | 38912 KB |
17.txt | AC | 240 ms | 38912 KB |
18.txt | AC | 284 ms | 38912 KB |
19.txt | AC | 257 ms | 38912 KB |
2.txt | AC | 11 ms | 34688 KB |
20.txt | AC | 257 ms | 38912 KB |
21.txt | AC | 265 ms | 38912 KB |
22.txt | AC | 254 ms | 38912 KB |
23.txt | AC | 244 ms | 38912 KB |
24.txt | AC | 235 ms | 38912 KB |
25.txt | AC | 235 ms | 38912 KB |
26.txt | AC | 288 ms | 38912 KB |
27.txt | AC | 275 ms | 38912 KB |
28.txt | AC | 275 ms | 38912 KB |
29.txt | AC | 238 ms | 38912 KB |
3.txt | AC | 299 ms | 38912 KB |
30.txt | AC | 239 ms | 38912 KB |
31.txt | AC | 240 ms | 38912 KB |
32.txt | AC | 240 ms | 38912 KB |
33.txt | AC | 241 ms | 38912 KB |
34.txt | AC | 241 ms | 38912 KB |
4.txt | AC | 297 ms | 38912 KB |
5.txt | AC | 11 ms | 34816 KB |
6.txt | AC | 11 ms | 34688 KB |
7.txt | AC | 294 ms | 38912 KB |
8.txt | AC | 294 ms | 38912 KB |
9.txt | AC | 276 ms | 38912 KB |
sample1.txt | AC | 10 ms | 34688 KB |
sample2.txt | AC | 10 ms | 34688 KB |
sample3.txt | AC | 10 ms | 34688 KB |