Cod sursa(job #3181390)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 6 decembrie 2023 22:45:47
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 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(int i1,int j1,int n,int m)
{

    int maxim=0,x=0,y=0;
    for(i=1;i<=200;i++)
        for(j=1;j<=200;j++)
            S[i][j]=0;
    for(int i=i1;i<=n;i++)
    {
        vector <int> Q;
        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(!Q.empty()&&S[i][j]<=S[i][Q.back()])
            {
                x=S[i][Q.back()];
                Q.pop_back();
                y=j-1;
                if(!Q.empty())
                    y=y-Q.back();
                else
                    y=y-j1+1;
                if(maxim<x*y)
                    maxim=x*y;
            }
            Q.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(1,1,n,i);
        D2=dr(1,i+1,n,m);
        sol=max(sol,D1+D2);
    }
    for(int i=1;i<n;i++)
    {
        D1=dr(1,1,i,m);
        D2=dr(i+1,1,n,m);
        sol=max(sol,D1+D2);
    }
    fout<<sol;
    return 0;
}