Dang_Quan_10_Tin

Untitled

Mar 12th, 2020
309
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <fstream>
  5. #include <stack>
  6. using namespace std;
  7. using ll=long long;
  8. using ld=long double;
  9.  
  10. const int maxn=1e6 +2;
  11.  
  12. ll n,m,h[1002],Max=-1,Left[10002],Right[10002];
  13. char x[1002][1002];
  14.  
  15. ll calc()
  16. {
  17.     stack<ll> S;
  18.     for(ll i = 1; i <= n; i++)
  19.     {
  20.         while(!S.empty() && h[S.top()] >= h[i])
  21.         {
  22.             S.pop();
  23.         }
  24.         Left[i] = S.empty() ? 0 : S.top();
  25.         S.push(i);
  26.     }
  27.     while(!S.empty()) S.pop();
  28.     for(ll i = n; i >= 1; i--)
  29.     {
  30.         while(!S.empty() && h[S.top()] >= h[i]) S.pop();
  31.         Right[i] = S.empty() ? n + 1 : S.top();
  32.         S.push(i);
  33.     }
  34.     ll res = 0;
  35.     for(ll i=1;i<=n;i++)
  36.     {
  37.         ll temp = (ll) h[i] * (Right[i]-Left[i]-1);
  38.         if(temp>res) res = temp;
  39.     }
  40.     return res;
  41. }
  42.  
  43. int main()
  44. {
  45.     //freopen("MAXRECT.INP","r",stdin);
  46.     //freopen("MAXRECT.OUT","w",stdout);
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(nullptr);
  49.     cout.tie(nullptr);
  50.     cin>>n>>m;
  51.     for(ll i=1;i<=n;i++)
  52.     {
  53.         for(ll j=1;j<=m;j++)
  54.         {
  55.             cin>>x[i][j];
  56.         }
  57.     }
  58.     for(ll i=1;i<=n;i++)
  59.     {
  60.         fill_n(h,1002,0);
  61.         fill_n(Left,1002,0);
  62.         fill_n(Right,1002,0);
  63.         for(ll j=1;j<=i;j++)
  64.         {
  65.             for(ll u=1;u<=m;u++)
  66.             {
  67.                 if(x[j][u]=='W') h[u]++;
  68.                 else h[u]=0;
  69.             }
  70.         }
  71.         ll res1 = calc();
  72.         Max = max(Max, res1);
  73.     }
  74.     cout << Max;
  75.  
  76. }
Advertisement
Add Comment
Please, Sign In to add comment