Cod sursa(job #3205170)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 19 februarie 2024 00:43:16
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
int test[201][201],mat[201][201],n,m;

void transfer( int x1,int y1,int x2,int y2)
{


    for( int i = x1; i <= x2; i ++ )
    {
        for ( int j = y1 ; j <= y2; j ++ )
        {
            test[i-x1+1][j-y1+1] = mat[i][j];

        }

    }

}

void liniar( vector<int> &st, vector<int> &dr, vector<int> &v, int n )
{
    stack<int> stiva;
    for ( int i = 1; i <= n ; i ++ )
    {
        while ( !stiva.empty() && v[stiva.top() ] > v[i])
        {
            dr[stiva.top()] = i ;
            stiva.pop();
        }
        stiva.push(i);
    }

    while (!stiva.empty() )
    {
        dr[stiva.top() ] = n + 1;
        stiva.pop();
    }

    for ( int i = n ; i >= 1 ; i -- )
    {
        while (!stiva.empty() && v[stiva.top()] > v[i])
        {
            st[stiva.top() ] = i ;
            stiva.pop();
        }
        stiva.push(i);
    }
    while (!stiva.empty())
    {
        st[stiva.top()] = 0 ;
        stiva.pop();
    }
}
int solve(int n, int m )
{

    int ans = 0 ;
    vector<int> h(m+2,0);

    for ( int i = 1; i <= n ; i ++ )
    {

        for ( int j = 1; j <= m ; j ++ )
        {

            if ( test[i][j] == 0)
                h[j] ++ ;
            else
                h[j] = 0 ;


        }


        vector<int> st(m+2);
        vector<int> dr (m+2);
        liniar(st,dr,h,m);

        for ( int j = 1; j <= m ; j ++ )
        {
            int cst = st[j] + 1;
            int cdr = dr[j] - 1;
            ans = max ( ans, ( cdr - cst + 1) * h[j]);
        }
    }

    return ans ;

}
int main()
{
    cin >> n >> m;

    int fin = 0 ;
    for ( int i = 1; i <= n ; i ++)
        for ( int j = 1; j <= m ; j ++ )
        {
            char c;
            cin >> c;
            if ( c== '1')
                mat[i][j] = 1;
        }

    for ( int i = 1; i <= n ; i ++ )
    {
        transfer(1,1,i,m);
        int val1 = solve(i,m);
        transfer(i +1, 1, n, m );
        int val2 = solve(n - i,m);
        fin = max ( fin, val2 + val1) ;
    }

    for( int i = 1 ; i <= m ; i ++ )
    {
        transfer(1,1,n,i);
        int val1 = solve(n,i);
        transfer(1,i+1,n,m);
        int val2 = solve(n, m - i );
        fin = max ( fin ,val1 + val2);
    }
    cout << fin << '\n';
    return 0;
}