Cod sursa(job #3162961)

Utilizator tomaionutIDorando tomaionut Data 30 octombrie 2023 11:13:57
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, a[205][205], v[205], up[205], down[205], l[205], r[205], sol, st[205], dr[205], top, stv[205];
string s[205];

int Solve(int n)
{
    for (int i = 1; i <= n; ++i) {
        st[i] = 0;
        dr[i] = n + 1;
    }

    int vf = 0;

    for (int i = 1; i <= n; ++i) {
        while (vf&& v[i] < v[stv[vf]]) {
            dr[stv[vf]] = i;
            vf -= 1;
        }

        stv[++vf] = i;
    }

    vf = 0;

    for (int i = n; i > 0; --i) {
        while (vf && v[i] < v[stv[vf]]) {
            st[stv[vf]] = i;
            vf -= 1;
        }

        stv[++vf] = i;
    }

    int best = 0;

    for (int i = 1; i <= n; ++i) {
        best = max(best, v[i] * (dr[i] - st[i] - 1));
    }

    return best;

}

void ResetV()
{
    for (int i = 0; i <= 200; i++)
        v[i] = 0;
}

int32_t main()
{
    int i, j;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        fin >> s[i];
        s[i] = '%' + s[i];
    }

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            if (s[i][j] == '0')
                v[j]++;
            else
                v[j] = 0;
        up[i] = max(up[i - 1], Solve(m));
    }

    ResetV();

    for (i = n; i >= 1; i--)
    {
        for (j = 1; j <= m; j++)
            if (s[i][j] == '0')
                v[j]++;
            else
                v[j] = 0;
        down[i] = max(down[i + 1], Solve(m));
    }

    ResetV();

    for (j = 1; j <= m; j++)
    {
        for (i = 1; i <= n; i++)
            if (s[i][j] == '0')
                v[i]++;
            else
                v[i] = 0;

        l[j] = max(l[j - 1], Solve(n));
    }

    ResetV();

    for (j = m; j >= 1; j--)
    {
        for (i = 1; i <= n; i++)
            if (s[i][j] == 0)
                v[i]++;
            else
                v[i] = 0;

        r[j] = max(r[j + 1], Solve(n));
    }

    for (i = 0; i <= n; i++)
        sol = max(sol, up[i] + down[i + 1]);

    for (i = 0; i <= m; i++)
        sol = max(sol, l[i] + r[i + 1]);

    fout << sol << "\n";

    return 0;
}