Cod sursa(job #2356642)

Utilizator trifangrobertRobert Trifan trifangrobert Data 26 februarie 2019 20:28:23
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.93 kb
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

const int NMAX = 205;
int n, m;
char s[NMAX];
bool a[NMAX][NMAX], b[NMAX][NMAX];
int dUp[NMAX][NMAX], dDown[NMAX][NMAX];
int maxUp[NMAX], maxDown[NMAX];
int stg[NMAX], drp[NMAX], st[NMAX], top;
int dpUp[NMAX], dpDown[NMAX];
int best;

void Init()
{
    memset(dUp, 0, sizeof(dUp));
    memset(dDown, 0, sizeof(dDown));
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
        {
            if (a[i][j] == true)
                dUp[i][j] = 0;
            else
                dUp[i][j] = dUp[i - 1][j] + 1;
        }
    for (int i = n;i >= 1;--i)
        for (int j = 1;j <= m;++j)
        {
            if (a[i][j] == true)
                dDown[i][j] = 0;
            else
                dDown[i][j] = dDown[i + 1][j] + 1;
        }
    for (int i = 0;i <= n + 1;++i)
        dDown[i][0] = dDown[i][m + 1] = dUp[i][0] = dUp[i][m + 1] = -1;
    for (int i = 0;i <= m + 1;++i)
        dDown[0][i] = dDown[n + 1][i] = dUp[0][i] = dUp[n + 1][i] = -1;
}

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

void CreateStg(int line, bool ok)
{
    top = 0;
    st[top] = 0;
    for (int i = 1;i <= m;++i)
    {
        if (ok == true)
            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];
        st[++top] = i;
    }
}

void CreateDrp(int line, bool ok)
{
    top = 0;
    st[top] = m + 1;
    for (int i = m;i >= 1;--i)
    {
        if (ok == true)
            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;
        st[++top] = i;
    }
}


int main()
{
    ifstream fin("bmatrix.in");
    ofstream fout("bmatrix.out");
    fin >> n >> m;
    for (int i = 1;i <= n;++i)
    {
        fin >> (s + 1);
        for (int j = 1;j <= m;++j)
            a[i][j] = (s[j] == '1');
    }
    Init();
    int bestUp, bestDown;
    for (int i = 1;i < n;++i)
    {
        bestUp = bestDown = 0;
        CreateStg(i, true);
        CreateDrp(i, true);
        for (int j = 1;j <= m;++j)
            bestUp = max(bestUp, dUp[i][j] * (stg[j] + drp[j] - 1));
        dpUp[i] = bestUp;
        CreateStg(i + 1, false);
        CreateDrp(i + 1, false);
        for (int j = 1;j <= m;++j)
            bestDown = max(bestDown, dDown[i][j] * (stg[j] + drp[j] - 1));
        dpDown[i] = bestDown;
    }
    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)
        best = max(best, dpDown[i + 1] + dpUp[i]);
    Rotate();
    Init();
    for (int i = 1;i < n;++i)
    {
        bestUp = bestDown = 0;
        CreateStg(i, true);
        CreateDrp(i, true);
        for (int j = 1;j <= m;++j)
            bestUp = max(bestUp, dUp[i][j] * (stg[j] + drp[j] - 1));
        dpUp[i] = bestUp;
        CreateStg(i + 1, false);
        CreateDrp(i + 1, false);
        for (int j = 1;j <= m;++j)
            bestDown = max(bestDown, dDown[i][j] * (stg[j] + drp[j] - 1));
        dpDown[i] = bestDown;
    }
    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)
        best = max(best, dpDown[i + 1] + dpUp[i]);
    fout << best << "\n";
    fin.close();
    fout.close();
    return 0;
}