Cod sursa(job #3289622)

Utilizator AswVwsACamburu Luca AswVwsA Data 27 martie 2025 17:48:36
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.79 kb
//dupa putin cuget, am realizat ca poti sa iei la fiecare linie
//si sa te intrebi "care este cel mai mare dreptunghi cu 0uri
//care se gaseste in toate liniile mai mici decat linia curenta",
//iar pe asta sa-l combini cu cel mai mare dreptunghi de 0uri din
//sufix
//Daca faci chestia asta, iei 56, doua cazuri picate si picate
//din bun simt
//E nevoie sa faci aceeasi chestie si pe coloane, intrucat
//exista cazuri precum 0010 unde totul este la fel, mai putin
//coloanele (ideea e ca se intampla doar pentru dreptunghiuri cu
//o singura dimensiune, din motiv ca cele cu cel putin 2 unitati
//la lungime si la latime erau deja luate in considerare la linii,
//nu mai era nevoie si de coloane)
//Pentru a gasi maximele astea pe linii si pe coloane facem
//skyline, considerand liniile/coloanele cu 1 ca avand inaltime 0,
//iar pe restul ca fiind pana la primul 1 de mai sus sau marginea
//matricei
//O(n * m) surprinzator
#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;
}