Cod sursa(job #3334202)

Utilizator mtcmtcmtc mtc mtcmtc Data 16 ianuarie 2026 19:02:13
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <fstream>

using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
int a[205][205];
int zdr[205][205],zjos[205][205];
int sus[205],jos[205],st[205],dr[205];
char s[205];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=m;j++){
            a[i][j]=s[j-1]-'0';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int l=i,c=j;
            while(a[l][c]==0&&l<=n){
                zjos[i][j]++;
                l++;
            }
            l=i,c=j;
            while(a[l][c]==0&&c<=m){
                zdr[i][j]++;
                c++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0){
                int mn=zdr[i][j];
                int mx=mn;
                int l=i,c=j;
                while(a[l][c]==0&&l<=n){
                    sus[l]=max(sus[l],mx);
                    l++;
                    mn=min(mn,zdr[l][c]);
                    mx=(l-i+1)*mn;
                }
            }
        }
    }
    for(int i=n;i>0;i--){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0){
                int mn=zdr[i][j];
                int mx=mn;
                int l=i,c=j;
                while(a[l][c]==0&&l>0){
                    jos[l]=max(jos[l],mx);
                    l--;
                    mn=min(mn,zdr[l][c]);
                    mx=(i-l+1)*mn;
                }
            }
        }
    }
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            if(a[i][j]==0){
                int mn=zjos[i][j];
                int mx=mn;
                int l=i,c=j;
                while(a[l][c]==0&&c<=m){
                    st[c]=max(st[c],mx);
                    c++;
                    mn=min(mn,zjos[l][c]);
                    mx=(c-j+1)*mn;
                }
            }
        }
    }
    for(int j=m;j>0;j--){
        for(int i=1;i<=n;i++){
            if(a[i][j]==0){
                int mn=zjos[i][j];
                int mx=mn;
                int l=i,c=j;
                while(a[l][c]==0&&c>0){
                    dr[c]=max(dr[c],mx);
                    c--;
                    mn=min(mn,zjos[l][c]);
                    mx=(j-c+1)*mn;
                }
            }
        }
    }

    for(int i=1;i<=n;i++) sus[i]=max(sus[i],sus[i-1]);
    for(int i=n;i>0;i--) jos[i]=max(jos[i],jos[i+1]);
    for(int j=1;j<=m;j++) st[j]=max(st[j],st[j-1]);
    for(int j=m;j>0;j--) dr[j]=max(dr[j],dr[j+1]);

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

    cout<<ans;
    return 0;
}