Cod sursa(job #3312432)

Utilizator coldsh1tANdrei coldsh1t Data 28 septembrie 2025 11:13:59
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <iostream>
#include <fstream>

using namespace std;

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

char a[205][205];
int v[205], st[205], dr[205], sus[205], jos[205];

int main()
{
    int n, m, sol=0;

    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            fin>>a[i][j];
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(a[i][j]=='0')
            {
                v[j]++;
            }
            else
            {
                v[j]=0;
            }
            int x=10005, y=0;
            for(int k=j; k>=1; k--)
            {
                x=min(x,v[k]);
                y=max(y,x*(j-k+1));
            }
            if(st[j]<max(st[j-1], y))
            {
                st[j]=max(st[j-1], y);
            }
            if(sus[i]<max(sus[i-1], y))
            {
                sus[i]=max(sus[i-1], y);
            }
        }
    }
    for(int j=1;j<=m;j++)
    {
        v[j]=0;
    }
    for(int i=n; i>0; i--)
    {
        for(int j=m; j>0; j--)
        {
            if(a[i][j]=='0')
            {
                v[j]++;
            }
            else
            {
                v[j]=0;
            }
            int x=10005, y=0;
            for(int k=j; k<=m; k++)
            {
                x=min(x,v[k]);
                y=max(y,x*(k-j+1));
            }

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