Cod sursa(job #2630121)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 24 iunie 2020 14:00:35
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.02 kb
#include <bits/stdc++.h>
#define maxn 205

std::ifstream fin ("bmatrix.in");
std::ofstream fout ("bmatrix.out");

bool a[maxn][maxn];
int upRow[maxn], downRow[maxn], leftCol[maxn], rightCol[maxn];
int h[maxn];

std::stack <int> stack;

int main()
{
    int n, m, i, j, max=0, index, height;
    char chr;
    fin >> n >>  m;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++){
            fin >> chr;
            a[i][j] = chr - '0';
        }


    /// Up Row
    memset (h, 0, sizeof h);
    for (i=1; i<=n; i++){
        for (j=1; j<=m; j++){
            if (a[i][j] == 0)
                h[j] ++;
            else h[j] = 0;
        }

        while (stack.empty() == false)
            stack.pop();
        h[0] = -1;
        h[m+1] = -1;
        stack.push (0);
        max = 0;
        for (j=1; j<=m+1; j++){
            //std::cout << stack.top() << '\n';
            while (stack.empty() == false and h[stack.top()] >= h[j]){
                height = h[stack.top()];
                stack.pop();
                if (stack.empty() == false)
                    max = std::max (max, height * (j-stack.top()-1));
            }
            stack.push (j);
        }

        upRow[i] = std::max(max, upRow[i-1]);
        //fout << upRow[i] << '\n';
    }

    /// Down Row
    memset (h, 0, sizeof h);
    for (i=n; i>0; i--){
        for (j=1; j<=m; j++){
            if (a[i][j] == 0)
                h[j] ++;
            else h[j] = 0;
        }

        while (stack.empty() == false)
            stack.pop();
        h[0] = -1;
        h[m+1] = -1;
        stack.push (0);
        max = 0;
        for (j=1; j<=m+1; j++){
            //std::cout << stack.top() << '\n';
            while (stack.empty() == false and h[stack.top()] >= h[j]){
                height = h[stack.top()];
                stack.pop();
                if (stack.empty() == false)
                    max = std::max (max, height * (j-stack.top()-1));
            }
            stack.push (j);
        }

        downRow[i] = std::max(max, downRow[i+1]);
        //fout << downRow[i] << '\n';
    }

    ///Left Column
    memset (h, 0, sizeof h);
    for (j=1; j<=m; j++){
        for (i=1; i<=n; i++){
            if (a[i][j] == 0)
                h[i] ++;
            else h[i] = 0;
        }

        while (stack.empty() == false)
            stack.pop();
        h[0] = -1;
        h[n+1] = -1;
        stack.push (0);
        max = 0;
        for (i=1; i<=n+1; i++){
            //std::cout << stack.top() << '\n';
            while (stack.empty() == false and h[stack.top()] >= h[i]){
                height = h[stack.top()];
                stack.pop();
                if (stack.empty() == false)
                    max = std::max (max, height * (i-stack.top()-1));
            }
            stack.push (i);
        }

        leftCol[j] = std::max(max, leftCol[j-1]);
        //fout << leftCol[j] << '\n';
    }

    ///Right Column
    memset (h, 0, sizeof h);
    for (j=m; j>0; j--){
        for (i=1; i<=n; i++){
            if (a[i][j] == 0)
                h[i] ++;
            else h[i] = 0;
        }

        while (stack.empty() == false)
            stack.pop();
        h[0] = -1;
        h[n+1] = -1;
        stack.push (0);
        max = 0;
        for (i=1; i<=n+1; i++){
            //std::cout << stack.top() << '\n';
            while (stack.empty() == false and h[stack.top()] >= h[i]){
                height = h[stack.top()];
                stack.pop();
                if (stack.empty() == false)
                    max = std::max (max, height * (i-stack.top()-1));
            }
            stack.push (i);
        }

        rightCol[j] = std::max(max, rightCol[j+1]);
        //fout << rightCol[j] << '\n';
    }

    max = 0;
    for (i=1; i<n; i++)
        max = std::max (max, upRow[i] + downRow[i+1]);
    for (i=1; i<m; i++)
        max = std::max (max, leftCol[i] + rightCol[i+1]);

    fout << max << '\n';



    return 0;
}