Cod sursa(job #2955090)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 16 decembrie 2022 10:07:56
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.62 kb
/// Preset de infoarena
#include <fstream>
#include <vector>

using namespace std;

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

const int maxN = 205;
int n, m, mat[maxN][maxN], st[maxN], dr[maxN], max_st[maxN], max_dr[maxN], max_sus[maxN], max_jos[maxN], v[maxN], ans;
string str;

int skyline(int x) /// RIP VARENA, YOU WILL FOREVER BE MISSED
{
    vector <int> stiva;
    for(int i = 1; i <= x; i++)
    {
        while(!stiva.empty() && v[stiva.back()] >= v[i])
            stiva.pop_back();
        if(stiva.empty())
            st[i] = 1;
        else
            st[i] = stiva.back() + 1;
        stiva.push_back(i);
    }
    stiva.clear();
    for(int i = x; i >= 1; i--)
    {
        while(!stiva.empty() && v[stiva.back()] >= v[i])
            stiva.pop_back();
        if(stiva.empty())
            dr[i] = x;
        else
            dr[i] = stiva.back() - 1;
        stiva.push_back(i);
    }
    int arie = 0;
    for(int i = 1; i <= x; i++)
        arie = max(arie, v[i] * (dr[i] - st[i] + 1));
    return arie;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        fin >> str;
        for(int j = 1; j <= m; j++)
            mat[i][j] = str[j - 1] - '0';
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(mat[i][j] == 0)
                v[j]++;
            else
                v[j] = 0;
        }
        max_sus[i] = max(max_sus[i - 1], skyline(m));
    }
    for(int i = 1; i <= m; i++)
        v[i] = 0;
    for(int i = n; i >= 1; i--)
    {
        for(int j = 1; j <= m; j++)
        {
            if(mat[i][j] == 0)
                v[j]++;
            else
                v[j] = 0;
        }
        max_jos[i] = max(max_jos[i + 1], skyline(m));
    }
    for(int i = 1; i <= m; i++)
        v[i] = 0;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(mat[j][i] == 0)
                v[j]++;
            else
                v[j] = 0;
        }
        max_st[i] = max(max_st[i - 1], skyline(n));
    }
    for(int i = 1; i <= n; i++)
        v[i] = 0;
    for(int i = m; i >= 1; i--)
    {
        for(int j = 1; j <= n; j++)
        {
            if(mat[j][i] == 0)
                v[j]++;
            else
                v[j] = 0;
        }
        max_dr[i] = max(max_dr[i + 1], skyline(n));
    }
    for(int i = 1; i <= n; i++)
        ans = max(ans, max_sus[i] + max_jos[i + 1]);
    for(int i = 1; i <= m; i++)
        ans = max(ans, max_st[i] + max_dr[i + 1]);
    fout << ans;
    return 0;
}