Cod sursa(job #1992989)

Utilizator Alex18maiAlex Enache Alex18mai Data 22 iunie 2017 03:04:18
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <fstream>
#include <stack>

using namespace std;

ifstream cin ("bmatrix.in");
ofstream cout ("bmatrix.out");

char sir[205];
int A[205][205];
int aux[205][205];
int h[205][205];
int l[205][205];
int st[205];
int dr[205];
stack <int> lft;
stack <int> rgt;

void intors (int m, int n)
{
    for (int i=1; i<=m; i++)
    {
        for (int j=1; j<=n; j++)
        {
            aux[n-j+1][i] = A[i][j];
        }
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            A[i][j] = aux[i][j];
        }
    }
    return;
}
int sol (int m, int n)
{
    int solution=0;
    for (int k=1; k<=m; k++)
    {
        int up=0;
        int down=0;
        while (!lft.empty())
        {
            lft.pop();
        }
        while (!rgt.empty())
        {
            rgt.pop();
        }
        lft.push(0);
        rgt.push(n+1);
        for (int j=1; j<=n; j++)
        {
            while (h[k][j] <= h[k][lft.top()] && lft.size()>1)
            {
                lft.pop();
            }
            st[j]=lft.top();
            lft.push(j);
        }
        for (int j=n; j>=1; j--)
        {
            while (h[k][j] <= h[k][rgt.top()] && rgt.size()>1)
            {
                rgt.pop();
            }
            dr[j]=rgt.top();
            rgt.push(j);
        }
        for (int j=1; j<=n; j++)
        {
            up=max(up, h[k][j] * (dr[j] - st[j] -1));
        }
        //up done
        while (!lft.empty())
        {
            lft.pop();
        }
        while (!rgt.empty())
        {
            rgt.pop();
        }
        lft.push(0);
        rgt.push(n+1);
        for (int j=1; j<=n; j++)
        {
            while (l[k+1][j] <= l[k+1][lft.top()] && lft.size()>1)
            {
                lft.pop();
            }
            st[j]=lft.top();
            lft.push(j);
        }
        for (int j=n; j>=1; j--)
        {
            while (l[k+1][j] <= l[k+1][rgt.top()] && rgt.size()>1)
            {
                rgt.pop();
            }
            dr[j]=rgt.top();
            rgt.push(j);
        }
        for (int j=1; j<=n; j++)
        {
            down=max(down, l[k+1][j] * (dr[j] - st[j] -1));
        }
        //down done
        solution=max(solution, up + down);
    }
    return solution;
}

int main()
{
    int m, n;
    cin>>m>>n;
    for (int i=1; i<=m; i++)
    {
        cin>>(sir+1);
        for (int j=1; j<=n; j++)
        {
            A[i][j]=sir[j]-'0';
        }
    }
    for (int i=1; i<=m; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (A[i][j] == 0)
            {
                h[i][j] = h[i-1][j] + 1;
            }
            if (A[i][j] == 1)
            {
                h[i][j] = 0;
            }
        }
    }
    for (int i=m; i>=1; i--)
    {
        for (int j=1; j<=n; j++)
        {
            if (A[i][j] == 0)
            {
                l[i][j] = l[i+1][j] + 1;
            }
            else
            {
                l[i][j] = 0;
            }
        }
    }
    int s1 = sol(m,n);
    intors(m,n);
    int s2 = sol(n,m);
    cout<<max(s1, s2)<<'\n';
    return 0;
}