Cod sursa(job #3318019)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 26 octombrie 2025 16:28:36
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
#define INF 212
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");


int v[205][205], sus[205], jos[205], dr[205], st[205], n, m, h[205];
int calcArie( int dim )
{
    int stiva[205], k = 0, j, left[205], right[205];
    for ( j = 1; j <= dim + 1; ++j )
    {
        while ( k > 0 && h[stiva[k]] > h[j] )
        {
            right[stiva[k]] = j;
            --k;
        }
        stiva[++k] = j;
    }

    k = 0;
    for ( j = dim; j >= 0; --j )
    {
        while ( k > 0 && h[stiva[k]] > h[j] )
        {
            left[stiva[k]] = j;
            --k;
        }
        stiva[++k] = j;
    }

    int maxim = -1;
    for ( j = 1; j <= dim; ++j )
    {
      //  fout << left[j] << " " << right[j] << endl;
        int arie = h[j] * (right[j] - left[j] - 1);
        maxim = max(maxim, arie);
    }
    return maxim;

}
int main()
{
    int i, j;
    fin >> n >> m;
    for ( i = 1; i <= n; ++i )
        for ( j = 1; j <= m; ++j )
        {
            char c;
            fin >> c;
            v[i][j] = c - '0';
        }

    h[0] = h[m + 1] = -INF;
    for ( i = 1; i <= n; ++i )
    {
        for ( j = 1; j <= m; ++j )
        {
            if ( v[i][j] == 0 )
                ++h[j];
            else
                h[j] = 0;
        }
        sus[i] = max( sus[i - 1], calcArie(m));
    }


    for ( j = 1; j <= m; ++j )
        h[j] = 0;
    for ( i = n; i >= 1; --i )
    {
        for ( j = 1; j <= m; ++j )
        {
            if ( v[i][j] == 0 )
                ++h[j];
            else
                h[j] = 0;
        }
        jos[i] = max(jos[i + 1], calcArie(m));
    }

    int sol = -1;
    for ( i = 1; i < n; ++i )
        sol = max(sol, sus[i] + jos[i + 1]);

    fout << sol << '\n';
    return 0;
    h[0] = h[n + 1] = -INF;
    for ( j = 1; j <= m; ++j )
    {
        for ( i = 1; i <= n; ++i )
        {
            if ( v[i][j] == 0 )
                ++h[i];
            else
                h[i] = 0;
        }
        st[i] = max(st[i - 1], calcArie(n));
    }

    for ( i = 1; i <= n; ++i )
        h[i] = 0;
    for (j = m; j >= 1; --j )
    {
        for ( i = 1; i <= n; ++i )
        {
            if ( v[i][j] == 0 )
                ++h[i];
            else
                h[i] = 0;
        }
        dr[i] = max(dr[i + 1], calcArie(n));
    }

    for ( j = 1; j < m; ++j )
        sol = max(sol, st[j] + dr[j + 1]);

    fout << sol << '\n';
    return 0;
}