Cod sursa(job #2644273)

Utilizator Alin_StanciuStanciu Alin Alin_Stanciu Data 24 august 2020 09:47:40
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n0, m0, n, m, St[201][201], Ma[2][2][201];
bool A0[201][201], A[201][201];

void GetMax(bool oriz, bool inv)
{
    n = oriz ? n0 : m0, m = oriz ? m0 : n0;
    for (int i0 = 1; i0 <= n0; ++i0)
    {
        for (int j0 = 1; j0 <= m0; ++j0)
        {
            int i = oriz ? i0 : j0, j = oriz ? j0 : i0;
            i = inv ? n - i + 1 : i;
            A[i][j] = A0[i0][j0];
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        Ma[oriz][inv][i] = Ma[oriz][inv][i - 1];
        for (int j = 1; j <= m; ++j)
        {
            if (!A[i][j])
            {
                St[i][j] = St[i][j - 1] + 1;
                int stmin = 2000000000;
                for (int k = i; k >= 1 && !A[k][j]; --k)
                {
                    stmin = min(stmin, St[k][j]);
                    Ma[oriz][inv][i] = max(Ma[oriz][inv][i], stmin * (i - k + 1));
                }
            }
            else St[i][j] = 0;
        }

    }
}

int main()
{
    fin >> n0 >> m0;
    for (int i = 1; i <= n0; ++i)
    {
        for (int j = 1; j <= m0; ++j)
        {
            char c;
            fin >> c;
            A0[i][j] = c == '1';
        }
    }
    GetMax(true, false);
    GetMax(true, true);
    GetMax(false, false);
    GetMax(false, true);

    int ma = 0;
    for (int i = 1; i < n0; ++i)
        ma = max(ma, Ma[true][false][i] + Ma[true][true][n0 - i]);
    for (int j = 1; j < m0; ++j)
        ma = max(ma, Ma[false][false][j] + Ma[false][true][m0 - j]);
    fout << ma;

    return 0;
}