// compile: g++ data.cpp /usr/include/c++/12/debug/cpglib/print.o -o data -O1 -std=gnu++20 -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -fmax-errors=2 -DLOCAL // run: time ./data < data.in #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #ifdef LOCAL #include <debug/cpglib/print.h> #define debug(x...) _debug_print(0, #x, x); #define Debug(x...) _debug_print(1, #x, x); #define DEBUG(x...) _debug_print(2, #x, x); std::ifstream terminal("/dev/tty"); #define PP cerr<<"![1;30mpause...\e[0m",terminal.ignore(); #else #define debug(x...) #define Debug(x...) #define DEBUG(x...) #define PP #endif template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;} #define rep(i,a,b) for(int i=(a);i<(int)(b);++i) #define sz(v) ((int)(v).size()) #define print(...) print_(__VA_ARGS__); #define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0) #define cmin(x,...) x=min({(x),__VA_ARGS__}) #define cmax(x,...) x=max({(x),__VA_ARGS__}) #define INTMAX (int)(9223372036854775807) #define INF (int)(1152921504606846976) #define NaN (int)(0x8b88e1d0595d51d1) #define double long double #define int long long #define uint unsigned long long #define endl "\n" #define MAXN 200010 int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; vector<vector<bool>> a(n, vector<bool>(m, 0)); vector<queue<int>> col(m); rep(i, 0, n) { string s; cin >> s; rep(j, 0, m) { a[i][j] = s[j] == '*'; if (a[i][j]) col[j].push(i); } } rep(j, 0, m) col[j].push(n); int ans = 0; rep(i, 0, n) { // first: start col, second: height stack<pair<int, int>> st; rep(j, 0, m) if (col[j].size() && col[j].front() < i) col[j].pop(); rep(j, 0, m) { int sc = j; // start col while (st.size() && st.top().second > col[j].front() - i) { auto [c, h] = st.top(); st.pop(); cmax(ans, (j - c) * h); sc = c; } st.push({sc, col[j].front() - i}); } while (st.size()) { auto [c, h] = st.top(); st.pop(); cmax(ans, (m - c) * h); } } cout << ans << endl; return 0; }
No Comments