Cod sursa(job #2218507)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 4 iulie 2018 18:17:07
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.82 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 210;
int n, m;
char a[NMAX][NMAX];
char b[NMAX][NMAX];
int dUp[NMAX][NMAX], dDown[NMAX][NMAX];
int st[NMAX], top;
int stg[NMAX], drp[NMAX];
int ans = 0;
int dpUp[NMAX], dpDown[NMAX];

void Read()
{
    ifstream fin("bmatrix.in");
    fin >> n >> m;
    for (int i = 1;i <= n;++i)
        fin >> (a[i] + 1);
    fin.close();
}

void Initialize()
{
    for (int i = 0;i <= n + 1;++i)
        for (int j = 0;j <= m + 1;++j)
            dUp[i][j] = dDown[i][j] = 0;
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
            a[i][j] == '0' ? dUp[i][j] = dUp[i - 1][j] + 1 : dUp[i][j] = 0;
    for (int i = n;i >= 1;--i)
        for (int j = 1;j <= m;++j)
            a[i][j] == '0' ? dDown[i][j] = dDown[i + 1][j] + 1 : dDown[i][j] = 0;
}

void Rotate()
{
    int p = n;
    for (int i = 1;i <= n;++i)
    {
        for (int j = 1;j <= m;++j)
            b[j][p] = a[i][j];
        --p;
    }
    swap(n, m);
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
            a[i][j] = b[i][j];
    for (int i = 1;i <= n;++i)
        a[i][m + 1] = 0;
    for (int j = 1;j <= m;++j)
        a[n + 1][j] = 0;
}

void CreateStg(int line, bool ok)
{
    if (ok)
        dUp[line][0] = -1;
    else
        dDown[line][0] = -1;
    top = 0;
    st[0] = 0;
    for (int i = 1;i <= m;++i)
    {
        if (ok)
            while (top > 0 && dUp[line][i] <= dUp[line][st[top]])
                --top;
        else
            while (top > 0 && dDown[line][i] <= dDown[line][st[top]])
                --top;
        stg[i] = i - st[top] - 1;
        st[++top] = i;
    }
}

void CreateDrp(int line, bool ok)
{
    if (ok)
        dUp[line][m + 1] = -1;
    else
        dDown[line][m + 1] = -1;
    top = 0;
    st[0] = m + 1;
    for (int i = m;i >= 1;--i)
    {
        if (ok)
            while (top > 0 && dUp[line][i] <= dUp[line][st[top]])
                --top;
        else
            while (top > 0 && dDown[line][i] <= dDown[line][st[top]])
                --top;
        drp[i] = st[top] - i - 1;
        st[++top] = i;
    }
}

void Solve()
{
    int aux1, aux2;
    Initialize();
    for (int i = 1;i < n;++i)
    {
        aux1 = aux2 = 0;
        CreateStg(i, true);
        CreateDrp(i, true);
        for (int j = 1;j <= m;++j)
            aux1 = max(aux1, (stg[j] + drp[j] + 1) * dUp[i][j]);
        CreateStg(i + 1, false);
        CreateDrp(i + 1, false);
        for (int j = 1;j <= m;++j)
            aux2 = max(aux2, (stg[j] + drp[j] + 1) * dDown[i + 1][j]);
        dpUp[i] = aux1;
        dpDown[i + 1] = aux2;
    }
    for (int i = 1;i < n;++i)
        dpUp[i] = max(dpUp[i - 1], dpUp[i]);
    for (int i = n;i > 1;--i)
        dpDown[i] = max(dpDown[i + 1], dpDown[i]);
    for (int i = 1;i < n;++i)
        ans = max(ans, dpUp[i] + dpDown[i + 1]);
    Rotate();
    Initialize();
    for (int i = 1;i < n;++i)
    {
        aux1 = aux2 = 0;
        CreateStg(i, true);
        CreateDrp(i, true);
        for (int j = 1;j <= m;++j)
            aux1 = max(aux1, (stg[j] + drp[j] + 1) * dUp[i][j]);
        CreateStg(i + 1, false);
        CreateDrp(i + 1, false);
        for (int j = 1;j <= m;++j)
            aux2 = max(aux2, (stg[j] + drp[j] + 1) * dDown[i + 1][j]);
        dpUp[i] = aux1;
        dpDown[i] = aux2;
    }
    for (int i = 1;i < n;++i)
        dpUp[i] = max(dpUp[i - 1], dpUp[i]);
    for (int i = n;i > 1;--i)
        dpDown[i] = max(dpDown[i + 1], dpDown[i]);
    for (int i = 1;i < n;++i)
        ans = max(ans, dpUp[i] + dpDown[i + 1]);
}

void Write()
{
    ofstream fout("bmatrix.out");
    fout << ans << "\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}