Cod sursa(job #2653799)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 29 septembrie 2020 09:13:53
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout("bmatrix.out");
int n,m,h[205],st[205],solsus[205],soljos[205],solst[205],soldr[205];
char s[205];
bool a[202][202];

int hist (int dim)
{
    int i,vf=0,sol=-2;
    st[++vf]=0;
    for (i=1;i<=dim+1;i++)
    {
        while (vf!=0 && h[st[vf]]>=h[i])
        {
            sol=max(sol,h[st[vf]]*(i-1-(st[vf-1]+1)+1));
            --vf;
        }
        st[++vf]=i;
    }
    return sol;
}

int main()
{
    fin>>n>>m;
    fin.get();
    int i,j,sol=0;
    for (i=1;i<=n;i++)
    {
        fin.getline(s,m+2);
        for (j=1;j<=m;j++)
            a[i][j]=s[j-1]-'0';
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
            if (a[i][j]==0)
                h[j]++;
        else    h[j]=0;
        solsus[i]=max(solsus[i-1],hist(m));
    }
    for (j=1;j<=m;j++)
        h[j]=!(a[n][j]);
    soljos[n]=hist(m);
    for (i=n-1;i>0;--i)
    {
        for (j=1;j<=m;j++)
            if (a[i][j]==0)
                h[j]++;
        else    h[j]=0;
        soljos[i]=max(soljos[i+1],hist(m));
    }
    for (i=1;i<=n;i++)
        h[i]=!(a[i][1]);
    solst[1]=hist(n);
    for (j=2;j<=m;j++)
    {
        for(i=1;i<=n;i++)
            if (a[i][j]==0)
                h[i]++;
        else    h[i]=0;
        solst[j]=max(solst[j-1],hist(n));
    }
    for (i=1;i<=n;i++)
        h[i]=!(a[i][m]);
    soldr[m]=hist(n);
    for (j=m-1;j>0;--j)
    {
        for(i=1;i<=n;i++)
            if (a[i][j]==0)
                h[i]++;
        else    h[i]=0;
        solst[j]=max(solst[j+1],hist(n));
    }
    for (i=1;i<n;i++)
        sol=max(sol,solsus[i]+soljos[i+1]);
    for (j=1;j<m;j++)
        sol=max(sol,solst[j]+soldr[j+1]);
    fout<<sol<<'\n';
    return 0;
}