Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <fstream>
- #include <stack>
- using namespace std;
- using ll=long long;
- using ld=long double;
- const int maxn=1e6 +2;
- ll n,m,h[1002],Max=-1,Left[10002],Right[10002];
- char x[1002][1002];
- ll calc()
- {
- stack<ll> S;
- for(ll i = 1; i <= n; i++)
- {
- while(!S.empty() && h[S.top()] >= h[i])
- {
- S.pop();
- }
- Left[i] = S.empty() ? 0 : S.top();
- S.push(i);
- }
- while(!S.empty()) S.pop();
- for(ll i = n; i >= 1; i--)
- {
- while(!S.empty() && h[S.top()] >= h[i]) S.pop();
- Right[i] = S.empty() ? n + 1 : S.top();
- S.push(i);
- }
- ll res = 0;
- for(ll i=1;i<=n;i++)
- {
- ll temp = (ll) h[i] * (Right[i]-Left[i]-1);
- if(temp>res) res = temp;
- }
- return res;
- }
- int main()
- {
- //freopen("MAXRECT.INP","r",stdin);
- //freopen("MAXRECT.OUT","w",stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cin>>n>>m;
- for(ll i=1;i<=n;i++)
- {
- for(ll j=1;j<=m;j++)
- {
- cin>>x[i][j];
- }
- }
- for(ll i=1;i<=n;i++)
- {
- fill_n(h,1002,0);
- fill_n(Left,1002,0);
- fill_n(Right,1002,0);
- for(ll j=1;j<=i;j++)
- {
- for(ll u=1;u<=m;u++)
- {
- if(x[j][u]=='W') h[u]++;
- else h[u]=0;
- }
- }
- ll res1 = calc();
- Max = max(Max, res1);
- }
- cout << Max;
- }
Advertisement
Add Comment
Please, Sign In to add comment