Cod sursa(job #3247706)

Utilizator vicvicGriga Victor-Cristian vicvic Data 8 octombrie 2024 20:42:31
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <stack>
using namespace std;
ifstream f ("bmatrix.in");
ofstream g ("bmatrix.out");
int n, m, mat[205][205], pref_linie[205], pref_coloana[205], suf_linie[205], suf_coloana[205], st[205], dr[205], h[205], stiva[205], cnt;
void actst (int l)
{
    stiva[0]=0;
    for (int i=1;i<=l;i++)
    {
        while (stiva[0] && h[stiva[stiva[0]]]>=h[i])
        {
            stiva[0]--;
        }
        if (!stiva[0])
        {
            st[i]=0;
        }
        else st[i]=stiva[stiva[0]];
        stiva[++stiva[0]]=i;
    }
}
void actdr (int l)
{
    stiva[0]=0;
    for (int i=l;i>=1;i--)
    {
        while (stiva[0] && h[stiva[stiva[0]]]>=h[i])
        {
            stiva[0]--;
        }
        if (!stiva[0])
        {
            dr[i]=l+1;
        }
        else dr[i]=stiva[stiva[0]];
        stiva[++stiva[0]]=i;
    }
}
void skyline (int l)
{
    actst (l);
    actdr (l);
}
void actmx (int *v, int l, int ind, int coef)
{
    v[ind]=v[ind+coef];
    for (int i=1;i<=l;i++)
    {
        if (h[i]) v[ind]=max (v[ind], h[i]*(dr[i]-st[i]-1));
    }
}
void reset_h ()
{
    for (int i=1;i<=max (n, m);i++)
    {
        h[i]=0;
    }
}
int main()
{
    f >> n >> m;
    for (int i=1;i<=n;i++)
    {
        string s;
        f >> s;
        for (int j=1;j<=m;j++)
        {
            mat[i][j]=s[j-1]-'0';
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            h[j]=(mat[i][j]==1?0:h[j]+1);
        }
        skyline (m);
        actmx (pref_linie, m, i, -1);
    }
    reset_h ();
    for (int i=n;i>=1;i--)
    {
        for (int j=1;j<=m;j++)
        {
            h[j]=(mat[i][j]==1?0:h[j]+1);
        }
        skyline (m);
        actmx (suf_linie, m, i, 1);
    }
    reset_h ();
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=n;j++)
        {
            h[j]=(mat[j][i]==1?0:h[j]+1);
        }
        skyline (n);
        actmx (pref_coloana, n, i, -1);
    }
    reset_h ();
    for (int i=m;i>=1;i--)
    {
        for (int j=1;j<=n;j++)
        {
            h[j]=(mat[j][i]==1?0:h[j]+1);
        }
        skyline (n);
        actmx (suf_coloana, n, i, 1);
    }
    int rasp=0;
    for (int i=1;i<=n;i++)
    {
        rasp=max (rasp, pref_linie[i]+suf_linie[i+1]);
    }
    for (int i=1;i<=m;i++)
    {
        rasp=max (rasp, pref_coloana[i]+suf_coloana[i+1]);
    }
    g << rasp;
    return 0;
}