Cod sursa(job #2839913)

Utilizator Maniu_DianaManiu Maria Diana Maniu_Diana Data 26 ianuarie 2022 18:44:18
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, sus[205][205], jos[205][205], st[205], dr[205], dpsus[205], dpjos[205], v[205];
char a[205][205], inv[205][205];
int ans;

stack < pair < int , int > > L;

void read()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            fin >> a[i][j];
            inv[j][i] = a[i][j];
        }
    }
}

void sum(char c[205][205])
{
    for(int j = 1; j <= m; j ++) // fac sum pe col
    {
        for(int i = 1; i <= n; i ++)
        {
            if(c[i][j] == '0')
                sus[i][j] = sus[i - 1][j] + 1;
            else sus[i][j] = 0;
        }

        for(int i = n; i >= 1; i --)
        {
            if(c[i][j] == '0')
                jos[i][j] = jos[i + 1][j] + 1;
            else jos[i][j] = 0;
        }
    }
}

int maxim()
{
    int ma = 0;
    while(!L.empty())
        L.pop();

    L.push(make_pair(-1, 0));
    for(int i = 1; i <= m; i ++)
    {
        while(!L.empty() && v[i] <= L.top().first)
            L.pop();
        st[i] = i - L.top().second - 1;
        L.push(make_pair(v[i], i));
    }

    while(!L.empty())
        L.pop();

    L.push(make_pair(-1, m + 1));
    for(int i = m; i >= 1; i --)
    {
        while(!L.empty() && v[i] <= L.top().first)
            L.pop();
        dr[i] = L.top().second - i - 1;
        L.push(make_pair(v[i], i));
    }

    for(int i = 1; i <= m; i ++)
    {
        ma = max(ma, (dr[i] + st[i] + 1) * v[i]);
    }

    return ma;
}

void solve()
{
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            v[j] = sus[i][j];
        }
        dpsus[i] = max(dpsus[i - 1], maxim());
    }

    for(int i = n; i >= 1; i --)
    {
        for(int j = 1; j <= m; j ++)
        {
            v[j] = jos[i][j];
        }
        dpjos[i] = max(dpjos[i + 1], maxim());
    }

    for(int i = 1; i <= n; i ++)
    {
          ans = max(ans, dpsus[i] + dpjos[i + 1]);
    }

    for(int i = 1; i <= n; i ++)
        dpsus[i] = dpjos[i] = 0;
}

int main()
{
    read();
    sum(a);
    solve();
    swap(n, m);
    sum(inv);
    solve();
    fout << ans;
    return 0;
}