Cod sursa(job #2709617)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 20 februarie 2021 17:21:15
Problema BMatrix Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");

const int N = 205;
int n, m, h[N][N], up[N], down[N];
bool a[N][N], mat[N][N];
int area, maxArea;

void Read()
{
    fin >> n >> m;

    char s[N];
    for (int i = 1; i <= n; i++)
    {
        fin >> s;
        for (int j = 1; j <= m; j++)
            a[i][j] = s[j - 1] - '0';
    }
}

void Rotate()
{
    int b[N][N];
    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= n; i++)
            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];
}

void Solve()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            h[i][j] = (a[i][j] ? 0 : h[i - 1][j] + 1);
    for (int i = 1; i <= n; i++)
    {
        up[i] = up[i - 1];
        for (int j = 1; j <= m; j++)
        {
            int posSt, posDr;
            for (posDr = j; h[i][posDr] >= h[i][j]; posDr++);
            for (posSt = j; h[i][posSt] >= h[i][j]; posSt--);

            up[i] = max(up[i], h[i][j] * (posDr - posSt - 1));
        }
    }

    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            h[i][j] = (a[i][j] ? 0 : h[i + 1][j] + 1);
    for (int i = n; i >= 1; i--)
    {
        down[i] = down[i + 1];
        for (int j = 1; j <= m; j++)
        {
            int posSt, posDr;
            for (posDr = j; h[i][posDr] >= h[i][j]; posDr++);
            for (posSt = j; h[i][posSt] >= h[i][j]; posSt--);

            down[i] = max(down[i], h[i][j] * (posDr - posSt - 1));
        }
    }

    for (int i = 1; i < n; i++)
        maxArea = max(maxArea, up[i] + down[i + 1]);

}

int main()
{
    Read();
    Solve();
    Rotate();
    Solve();
    fout << maxArea;
    return 0;
}