Cod sursa(job #2504493)

Utilizator FrostfireMagirescu Tudor Frostfire Data 4 decembrie 2019 23:24:55
Problema BMatrix Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <stack>
#define NMAX 200

using namespace std;

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

int n, m, ans, nr[NMAX+10][NMAX+10], h[NMAX+10], dr[NMAX+10], st[NMAX+10];
bool a[NMAX+10][NMAX+10], b[NMAX+10][NMAX+10];
char s[NMAX+10];
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, int line)
{   for(int i=1; i<=m; i++) h[i] = min(nr[poz][i], poz-line);
    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;
}

int solve()
{   int sol = 0;
    height();
    for(int l=1; l<n; l++)
        {   int sol1 = 0, sol2 = 0;
            for(int i=1; i<=l; i++) sol1 = max(sol1, skyline(i, 0));
            for(int i=l+1; i<=n; i++) sol2 = max(sol2, skyline(i, l));
            sol = max(sol, sol1 + sol2);
        }
    return sol;
}

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

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;
}