Cod sursa(job #3181398)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 6 decembrie 2023 22:57:53
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout("bmatrix.out");
int n,m,i,j,sol,S[205][205],D1,D2;
bool a[205][205];
char c;

int dr(bool a[205][205],int i1,int j1,int n,int m)
{

    int maxim=0,x=0,y=0;
    for(int i=0;i<=202;i++)
        for(int j=0;j<=202;j++)
            S[i][j]=0;
    for(int i=i1;i<=n;i++)
    {
        vector <int> V;
        for(int j=j1;j<=m+1;j++)
        {
            if(a[i][j])
                S[i][j]=0;
            else
                S[i][j]=S[i-1][j]+1;
            if(j==m+1)
                S[i][j]=0;
            while(!V.empty()&&S[i][j]<=S[i][V.back()])
            {
                x=S[i][V.back()];
                V.pop_back();
                y=j-1;
                if(!V.empty())
                    y=y-V.back();
                else
                    y=y-j1+1;
                if(maxim<x*y)
                    maxim=x*y;
            }
            V.push_back(j);
        }
    }
    return maxim;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            fin>>c;
            a[i][j]=c-'0';
        }
    }
    sol=0;
    for(i=1;i<m;i++)
    {
        D1=dr(a,1,1,n,i);
        D2=dr(a,1,i+1,n,m);
        sol=max(sol,D1+D2);
    }
    for(int i=1;i<n;i++)
    {
        D1=dr(a,1,1,i,m);
        D2=dr(a,i+1,1,n,m);
        sol=max(sol,D1+D2);
    }
    fout<<sol;
    return 0;
}