Cod sursa(job #3350477)

Utilizator CarenaMironov Cezar Luca Carena Data 8 aprilie 2026 17:41:28
Problema BMatrix Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <stack>

using namespace std;

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

const int NMAX=2e2+1;
int n[4], m[4], h[NMAX], l[NMAX], dp[4][NMAX];
bool a[4][NMAX][NMAX];
stack<int> st;
//0 - linia i in sus
//1 - linia n-i+1 in jos
//2 - coloana j la stanga
//3 - coloana m-j+1 la dreapta

void reset_st(int x)
{
    while(!st.empty())
        st.pop();
    st.push(x);
}

void calc_dp(int b)
{
    h[0]=h[m[b]+1]=-1;
    for(int j=1;j<=m[b];j++)
        h[j]=0;
    for(int i=1;i<=n[b];i++)
    {
        dp[b][i]=dp[b][i-1];
        reset_st(0);
        for(int j=1;j<=m[b];j++)
        {
            h[j]=(a[b][i][j]==1)?0:h[j]+1;
            while(h[j]<=h[st.top()])
                st.pop();
            l[j]=st.top();
            st.push(j);
        }
        reset_st(m[b]+1);
        for(int j=m[b];j>=1;j--)
        {
            while(h[j]<=h[st.top()])
                st.pop();
            dp[b][i]=max(dp[b][i], h[j]*(st.top()-l[j]-1));
            st.push(j);
        }
    }
}

int main()
{
    char ch;
    in>>n[0]>>m[0];
    n[1]=n[0], n[2]=n[3]=m[0];
    m[1]=m[0], m[2]=m[3]=n[0];
    for(int i=1;i<=n[0];i++)
        for(int j=1;j<=m[0];j++)
        {
            in>>ch;
            a[0][i][j]=(ch=='1');
            a[1][n[0]-i+1][j]=(ch=='1');
            a[2][j][i]=(ch=='1');
            a[3][m[0]-j+1][i]=(ch=='1');
        }
    for(int b=0;b<4;b++)
        calc_dp(b);
    int ans=0;
    for(int i=1;i<n[0];i++)
        ans=max(ans, dp[0][i]+dp[1][n[0]-i]);
    for(int j=1;j<m[0];j++)
        ans=max(ans, dp[2][j]+dp[2][m[0]-j]);
    out<<ans;
    return 0;
}