Cod sursa(job #2564377)

Utilizator PatriciaCretoiuCretoiu Patricia PatriciaCretoiu Data 1 martie 2020 20:52:45
Problema BMatrix Scor 48
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");

const int N = 205;
int n, m, i, j, ans;
char v[N][N];

int solve(int i1, int i2)
{
    int stk[N], hist[N], l;
    int area, maxarea = 0;
    for(int i = i1; i <= i2; i++)
    {
        l = 0;
        for(int j = 1; j <= m + 1; j++)
        {
            if(i == i1) hist[j] = (v[i][j]=='0');
            else if(v[i][j] == '1') hist[j] = 0;
            else hist[j]++;

            if(j == m + 1) hist[j] = 0;

            maxarea = max(maxarea, hist[j]);

            while(l>0 && hist[j]<hist[stk[l]])
            {
                area = hist[stk[l]] * (j - stk[l]);
                maxarea = max(maxarea, area);
                stk[l--] = 0;
            }

            stk[++l] = j;
        }
    }
    return maxarea;
}

int main()
{
    in >> n >> m;

    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            in >> v[i][j];

    for(i = 1; i <= n; i++)
        ans = max(ans, solve(1,i) + solve(i+1,n));


    out << ans;

    return 0;
}