Cod sursa(job #2839703)

Utilizator Maniu_DianaManiu Maria Diana Maniu_Diana Data 26 ianuarie 2022 13:34:07
Problema BMatrix Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 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; ///poate ramane val de dinainte
        }

        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 ++) /// merg pe coloane
    {
        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 ++) ///pt fiecare el de pe linie calculez aria pe intervalul st - dr
    {
//        if((dr[i] + st[i] + 1) * v[i] >= ma)
//            ma = (dr[i] + st[i] + 1) * v[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[i] = jos[i][j];
        }
        dpjos[i] = max(dpjos[i + 1], maxim());
    }

    for(int i = 1; i <= n; i ++)
    {
//        if(ans <= (dpsus[i] + dpjos[i + 1]))
//        {
//            //fout << dpsus[i] << " " << dpjos[i + 1] << endl;
//            ans = dpsus[i] + dpjos[i + 1];
//        }
          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;
}