Cod sursa(job #3316712)

Utilizator coldsh1tANdrei coldsh1t Data 20 octombrie 2025 10:16:25
Problema BMatrix Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.44 kb
#include <iostream>
#include <fstream>

#define NMAX 1005

using namespace std;

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

char c[NMAX][NMAX];
long long vsus[NMAX][NMAX],vjos[NMAX][NMAX],vst[NMAX][NMAX],vdr[NMAX][NMAX];
long long l[NMAX],r[NMAX],sus[NMAX],jos[NMAX],st[NMAX],dr[NMAX],s[NMAX];
int n,m;

void bordare()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(c[i][j]=='0')
                vsus[i][j]=vsus[i-1][j]+1;
            else vsus[i][j]=0;
        }
    }
    for(int i=n; i>=1; i--)
    {
        for(int j=1; j<=m; j++)
        {
            if(c[i][j]=='0')
                vjos[i][j]=vjos[i+1][j]+1;
            else vjos[i][j]=0;
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(c[i][j]=='0')
                vst[i][j]=vst[i][j-1]+1;
            else vst[i][j]=0;
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=m; j>=1; j--)
        {
            if(c[i][j]=='0')
                vdr[i][j]=vdr[i][j+1]+1;
            else vdr[i][j]=0;
        }
    }
}
int main()
{
    long long ans=0;
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            fin>>c[i][j];
        }
    }

    bordare();

    for(int i=1; i<=n; i++)
    {
        int k=0;
        s[0]=0;
        for(int j=1; j<=m; j++)
        {
            while(k>0 && vsus[i][j]<=vsus[i][s[k]])
            {
                k--;
            }
            l[j]=s[k];
            k++;
            s[k]=j;
        }

        k=0;
        s[0]=m+1;
        for(int j=m; j>=1; j--)
        {
            while(k>0 && vsus[i][j]<=vsus[i][s[k]])
            {
                k--;
            }
            r[j]=s[k];
            k++;
            s[k]=j;
        }
        for(int j=1; j<=m; j++)
        {
            sus[i]=max(sus[i], vsus[i][j]*(r[j]-l[j]-1));
        }
    }
    for(int i=n; i>=1; i--)
    {
        int k=0;
        s[0]=0;
        for(int j=1; j<=m; j++)
        {
            while(k>0 && vjos[i][j]<=vjos[i][s[k]])
            {
                k--;
            }
            l[j]=s[k];
            k++;
            s[k]=j;
        }

        k=0;
        s[0]=m+1;
        for(int j=m; j>=1; j--)
        {
            while(k>0&&vjos[i][j]<=vjos[i][s[k]])
            {
                k--;
            }
            r[j]=s[k];
            k++;
            s[k]=j;
        }
        for(int j=1; j<=m; j++)
        {
            jos[i]=max(jos[i],vjos[i][j]*(r[j]-l[j]-1));
        }
    }
    for(int j=1; j<=m; j++)
    {
        int k=0;
        s[0]=0;
        for(int i=1; i<=n; i++)
        {
            while(k>0 && vst[i][j]<=vst[s[k]][j])
            {
                k--;
            }
            l[i]=s[k];
            k++;
            s[k]=i;
        }
        k=0;
        s[0]=n+1;
        for(int i=n; i>=1; i--)
        {
            while(k>0 && vst[i][j]<=vst[s[k]][j])
            {
                k--;
            }
            r[i]=s[k];
            k++;
            s[k]=i;
        }
        for(int i=1; i<=n; i++)
        {
            st[j]=max(st[j], vst[i][j]*(r[i]-l[i]-1));
        }
    }
    for(int j=m; j>=1; j--)
    {
        int k=0;
        s[0]=0;
        for(int i=1; i<=n; i++)
        {
            while(k>0 && vdr[i][j] <= vdr[s[k]][j])
            {
                k--;
            }
            l[i]=s[k];
            k++;
            s[k]=i;
        }
        k=0;
        s[0]=n+1;
        for(int i=n; i>=1; i--)
        {
            while(k>0 && vdr[i][j]<=vdr[s[k]][j])
            {
                k--;
            }
            r[i]=s[k];
            k++;
            s[k]=i;
        }
        for(int i=1; i<=n; i++)
        {
            dr[j]=max(dr[j], vdr[i][j]*(r[i]-l[i]-1));
        }
    }

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



    for(int i=1; i<n; i++)
    {
        ans=max(ans,sus[i]+jos[i]);
    }
    for(int j=1; j<m; j++)
    {
        ans=max(ans,st[j]+dr[j]);
    }
    fout<<ans;
    return 0;
}