Cod sursa(job #3162944)

Utilizator tomaionutIDorando tomaionut Data 30 octombrie 2023 10:59:11
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 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)
{
    int i, x, ans = 0;
    top = 0;
    stv[top] = 0;
    for (i = 1; i <= n; i++)
    {
        x = v[i];
        while (top and v[stv[top]] >= x)
            top--;
        st[i] = i - stv[top] - 1;
        stv[++top] = i;
    }

    top = 0;
    stv[top] = n + 1;
    for (i = n; i >= 1; i--)
    {
        x = v[i];
        while (top and v[stv[top]] >= x)
            top--;
        dr[i] = stv[top] - i - 1;
        stv[++top] = i;
    }

    for (i = 1; i <= n; i++)
        ans = max(ans, v[i] * (st[i] + dr[i] + 1));

    return ans;

}

void ResetV(int n)
{
    for (int i = 1; i <= n; 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(m);

    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(m);

    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(n);

    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;
}