Cod sursa(job #2909910)

Utilizator francescom_481francesco martinut francescom_481 Data 16 iunie 2022 19:36:22
Problema BMatrix Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
#define cin fin
#define cout fout

#define N 205
int n, m, rez, maxim;
int stdr[N][N], drst[N][N], jossus[N][N], susjos[N][N];
int ansstdr[N], ansdrst[N], ansjossus[N], anssusjos[N];
char mat[N][N], c;

int hist(int row[], int c)
{
    stack<int> result;
    int top_val;
    int max_area = 0;
    int area = 0;
    int i = 1;
    while(i <= c) {
        if(result.empty() || row[result.top()] <= row[i]) {
            result.push(i++);
        }
        else {
            top_val = row[result.top()];
            result.pop();
            area = top_val * (i-1);
            if(!result.empty()) {
                area = top_val * (i - result.top() - 1);
            }
            max_area = max(max_area, area);
        }
    }

    while(!result.empty()) {
        top_val = row[result.top()];
        result.pop();
        area = top_val * (i-1);
        if(!result.empty()) {
            area = top_val * (i - result.top() - 1);
        }
        max_area = max(max_area, area);
    }
    return max_area;
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ;  j <= m ; j++)
        {
            cin >> c;
            mat[i][j] = c;
        }
    }
    rez = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            if(mat[i][j] == '0')
            {
                susjos[i][j] = susjos[i-1][j]+1;
            }
        }
        rez = max(rez,hist(susjos[i],m));
        anssusjos[i] = rez;
    }

    rez = 0;
    for(int i = n ; i ; i--)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            if(mat[i][j] == '0')
            {
                jossus[i][j] = jossus[i+1][j]+1;
            }
        }
        rez = max(rez,hist(jossus[i],m));
        ansjossus[i] = rez;
        maxim = max(maxim,ansjossus[i]+anssusjos[i-1]);
    }
    rez = 0;
    for(int j = 1 ; j <= m ; j++)
    {
        for(int i = 1 ; i <= n ; i++)
        {
            if(mat[i][j] == '0')
            {
                stdr[i][j] = stdr[i][j-1]+1;
            }
        }
        rez = max(rez,hist(stdr[j],n));
        ansstdr[j] = rez;
    }
    rez = 0;
    for(int j = m ; j ; j--)
    {
        for(int i = 1 ; i <= n ; i++)
        {
            if(mat[i][j] == '0')
            {
                drst[i][j] = drst[i][j+1]+1;
            }
        }
        rez = max(rez,hist(drst[j],n));
        ansdrst[j] = rez;
        maxim = max(maxim,ansdrst[j]+ansstdr[j-1]);
    }
    cout << maxim ;
    return 0;
}