Histogram Maximum Rectangular Area in a Histogram

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef int  ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<int,int>pii;
//typedef pair<int,pair<int,int>>piii;
//typedef pair<ll,pair<ll,ll>>plll;
//typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> orderedSet;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define sf(a) scanf("%I64d",&a)
#define pf(a) printf("%I64d\n",a)
#define mem(a,b)     memset(a,b,sizeof(a))
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define F first
#define S second
#define minheap int,vector<int>,greater<int>
//#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define BOUNDARY(i, j) ((i >= 0 && i < row) && (j >= 0 && j < column))
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
const int Max = 1005;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<int,int> &a, const pair<int,int> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}
//___________________________________________________________________________________________________________________
//                              CODE STARTS FROM HERE
//                               MU_Codefighter2019
//-------------------------------------------------------------------------------------------------------------------

int getMaxArea(int hist[], int n)
{

    stack<int> s;

    int max_area = 0; // Initialize max area
    int tp;  // To store top of stack
    int area_with_top; // To store area with top bar
                       // as the smallest bar

    int i = 0;
    while (i < n)
    {
        if (s.empty() || hist[s.top()] <= hist[i])
            s.push(i++);

        else
        {
            tp = s.top();  // store the top index
            s.pop();  // pop the top

            area_with_top = hist[tp] * (s.empty() ? i :
                                   i - s.top() - 1);

     //   cout<<area_with_top<<endl;
            // update max area, if needed
            if (max_area < area_with_top)
                max_area = area_with_top;
        }
    }


    while (s.empty() == false)
    {
        tp = s.top();
        s.pop();
        area_with_top = hist[tp] * (s.empty() ? i :
                                i - s.top() - 1);

        if (max_area < area_with_top)
            max_area = area_with_top;
    }

    return max_area;
}


 int main()
 {
     fastread();

     ll t,cas=1;

     cin>>t;

     while(t--)
     {
         ll n,ans=0,m;

         cin>>n>>m;

         ll hist[m+1]={0},j,a;

         string str;

         for(ll i=0; i<n; i++)
         {
             cin>>str;

             for(j=0; j<m; j++)
             {

               a=str[j]-'0';
                 if(a)hist[j]=0;

                 else hist[j]++;
             }

             ans=max(ans,getMaxArea(hist,m));
         }

       cout<<"Case "<<cas++<<": "<<ans<<endl;
     }
 }