Cod sursa(job #2504505)

Utilizator FrostfireMagirescu Tudor Frostfire Data 4 decembrie 2019 23:42:11
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

int n, m, ans, nr[210][210], h[210], dr[210], st[210], sus[210], jos[210];
bool a[210][210], b[210][210];
char s[210];
stack <int> stiva;

void height()
{   memset(nr, 0, sizeof(nr));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            {   if(a[i][j]) nr[i][j] = 0;
                else nr[i][j] = nr[i-1][j] + 1;
            }
}

int skyline(int poz)
{   for(int i=1; i<=m; i++) h[i] = nr[poz][i];
    while(!stiva.empty()) stiva.pop();
    stiva.push(1);
    st[1] = 0;
    for(int i=2; i<=m; i++)
        {   while(!stiva.empty() && h[i] <= h[stiva.top()]) stiva.pop();
            if(stiva.empty()) st[i] = 0;
            else st[i] = stiva.top();
            stiva.push(i);
        }
    while(!stiva.empty()) stiva.pop();
    stiva.push(m);
    dr[m] = m+1;
    for(int i=m-1; i>=1; i--)
        {   while(!stiva.empty() && h[i] <= h[stiva.top()]) stiva.pop();
            if(stiva.empty()) dr[i] = m+1;
            else dr[i] = stiva.top();
            stiva.push(i);
        }
    int sol = 0;
    for(int i=1; i<=m; i++) sol = max(sol, h[i] * (dr[i]-st[i]-1));
    return sol;
}

void rotate90()
{   for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++) b[i][j] = a[n-j+1][i];
    swap(n, m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) a[i][j] = b[i][j];
}

int solve()
{   memset(sus, 0, sizeof(sus));
    memset(jos, 0, sizeof(jos));
    int sol = 0;
    height();
    for(int l=1; l<=n; l++) sus[l] = max(sus[l-1], skyline(l));
    rotate90();
    rotate90();
    height();
    for(int l=1; l<=n; l++) jos[l] = max(jos[l-1], skyline(l));
    for(int i=1; i<n; i++) sol = max(sol, sus[n-i] + jos[i]);
    return sol;
}

int main()
{
    f >> n >> m;
    for(int i=1; i<=n; i++)
        {   f >> s;
            for(int j=0; j<m; j++) a[i][j+1] = s[j] - '0';
        }
    ans = solve();
    rotate90();
    ans = max(ans, solve());
    g << ans << '\n';
    return 0;
}