Cod sursa(job #2473610)

Utilizator DariusDCDarius Capolna DariusDC Data 13 octombrie 2019 21:44:36
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <bits/stdc++.h>
#define lim 205

using namespace std;

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

int sol;
int n, m;
int lin[lim][lim], col[lim][lim];
int v[lim];
char c[2];
int dp1[lim], dp2[lim];
int mat1[lim][lim], mat2[lim][lim];
int st[lim], dr[lim];

stack <int> stk;

inline int sum()
{
    st[1] = 0;
    stk.push(1);
    for (int i = 2; i <= m; i++)
    {
        while (!stk.empty() && v[i] <= v[stk.top()])
            stk.pop();
        if(v[i]==v[i-1]) st[i] = st[i-1] + 1;
        else if(v[i] > v[i-1]) st[i] = 0;
        else
        {
            if(stk.empty()) st[i] = i-1;
            else st[i] = (i - stk.top()- 1);
        }
        stk.push(i);
    }
    while (!stk.empty()) stk.pop();


    stk.push(m);
    dr[m] = 0;
    for (int i = m - 1; i >= 1; i--)
    {
        while (!stk.empty() && v[i] <= v[stk.top()])
            stk.pop();
         if(v[i]==v[i+1]) dr[i] = dr[i+1]+1;
        else if(v[i] > v[i+1]) dr[i] = 0;
        else
        {
            if(stk.empty()) dr[i] = (m-i);
            else dr[i] = (stk.top()- i - 1);
        }
        stk.push(i);
    }
    while (!stk.empty()) stk.pop();
    int s = 0;
    for (int i = 1; i <= m; i++)
        s = max(s, (st[i] + dr[i] + 1) * v[i]);
    return s;
}

inline void solve(int a[205][205])
{
    for (int i = 1; i <= m; i++)
        dp1[i] = dp2[i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 1)
                mat1[i][j] = 0;
            else
                mat1[i][j] = mat1[i - 1][j] + 1;
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            if (a[i][j])
                mat2[i][j] = 0;
            else
                mat2[i][j] = mat2[i + 1][j] + 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            v[j] = mat1[i][j];
        int x = sum();
        dp1[i] = max(dp1[i - 1], x);
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= m; j++)
            v[j] = mat2[i][j];
        int x = sum();
        dp2[i] = max(dp2[i + 1], x);
    }
    for (int i = 1; i <= n; i++)
        sol = max(sol, dp1[i] + dp2[i + 1]);
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            fin >> c[0];
            lin[i][j] = c[0] - '0';
            col[j][i] = c[0] - '0';
        }
    }
    solve(lin);
    swap(n, m);
    solve(col);
    fout << sol;
    return 0;
}