Cod sursa(job #2562543)

Utilizator PatriciaCretoiuCretoiu Patricia PatriciaCretoiu Data 29 februarie 2020 15:28:21
Problema BMatrix Scor 52
Compilator cpp-64 Status done
Runda penultimainaintedeotv Marime 1.28 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, hist[N], stk[N];
char v[N][N], vt[N][N];

int solve(char v[N][N], int i1, int i2)
{
    int area, maxarea=0, len=0;

    memset(hist,0,sizeof(hist));

    for(int i = i1; i <= i2; i++)
    {
        len = 0;
        for(int j = 1; j <= m + 1; j++)
        {
            if(v[i][j] == '1') hist[j]=0;
            else hist[j]++;

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

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

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

            stk[++len] = 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(v,1,i) + solve(v,i+1,n));

    swap(n, m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            vt[i][j] = v[j][i];

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

    out << ans;

    return 0;
}