Cod sursa(job #3289618)

Utilizator AswVwsACamburu Luca AswVwsA Data 27 martie 2025 17:43:34
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <fstream>
#include <cassert>
#include <climits>
#include <stack>
#define ll long long
using namespace std;

const int NMAX = 200;

void buildstacks(int h[], int st[], int dr[], int n)
{
    stack <int> stiva;
    int i;
    for (i = 1; i <= n; i++)
    {
        while (!stiva.empty() and h[stiva.top()] >= h[i])
            stiva.pop();
        if (stiva.empty())
            st[i] = 0;
        else
            st[i] = stiva.top();
        stiva.push(i);
    }
    while (!stiva.empty())
        stiva.pop();
    for (i = n; i >= 1; i--)
    {
        while (!stiva.empty() and h[stiva.top()] >= h[i])
            stiva.pop();
        if (stiva.empty())
            dr[i] = n + 1;
        else
            dr[i] = stiva.top();
        stiva.push(i);
    }
}

int compute_res(int h[], int st[], int dr[], int n)
{
    int i;
    int ans = 0;
    for (i = 1; i <= n; i++)
        ans = max(ans, h[i] * (dr[i] - st[i] - 1));
    return ans;
}

char s[NMAX + 1][NMAX + 1];

int preflin[NMAX + 1];
int suflin[NMAX + 2];
int prefcol[NMAX + 1];
int sufcol[NMAX + 2];

int h[NMAX + 1];
int st[NMAX + 1];
int dr[NMAX + 1];

int main()
{
    ifstream cin("bmatrix.in");
    ofstream cout("bmatrix.out");
    int n, m, i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            cin >> s[i][j];
        }
    int ans = 0;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            if (s[i][j] == '0')
                h[j]++;
            else
                h[j] = 0;
        buildstacks(h, st, dr, m);
        preflin[i] = max(preflin[i - 1], compute_res(h, st, dr, m));
    }
    ans = preflin[n];
    for (i = 1; i <= m; i++)
        h[i] = 0;
    for (i = n; i >= 1; i--)
    {
         for (j = 1; j <= m; j++)
            if (s[i][j] == '0')
                h[j]++;
            else
                h[j] = 0;
        buildstacks(h, st, dr, m);
        suflin[i] = max(suflin[i + 1], compute_res(h, st, dr, m));
    }
    for (i = 1; i <= m; i++)
        h[i] = 0;
    for (j = 1; j <= m; j++)
    {
        for (i = 1; i <= n; i++)
            if (s[i][j] == '0')
                h[i]++;
            else
                h[i] = 0;
        buildstacks(h, st, dr, n);
        prefcol[j] = max(prefcol[j - 1], compute_res(h, st, dr, n));
    }
    for (i = 1; i <= n; i++)
        h[i] = 0;
    for (j = m; j >= 1; j--)
    {
        for (i = 1; i <= n; i++)
            if (s[i][j] == '0')
                h[i]++;
            else
                h[i] = 0;
        buildstacks(h, st, dr, n);
        sufcol[j] = max(sufcol[j + 1], compute_res(h, st, dr, n));
    }
    for (i = 1; i < n; i++)
        ans = max(ans, preflin[i] + suflin[i + 1]);
    for (i = 1; i < m; i++)
        ans = max(ans, prefcol[i] + sufcol[i + 1]);

    cout << ans;
}