Cod sursa(job #3252980)

Utilizator vladsoartavlad sofronea vladsoarta Data 31 octombrie 2024 17:18:55
Problema BMatrix Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <string>
#include <stack>
using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
string s;
int susjos[202][202],jossus[202][202],m,n;

struct neighbor
{
    int st,dr;
};

int arie(int* v)
{
    stack<int>stk;
    neighbor stdr[202]= {};
    for(int i=1; i<=m; i++)
    {
        while(!stk.empty()&&v[stk.top()] >= v[i])
            stk.pop();

        if(!stk.empty())
            stdr[i].st = stk.top();
        stk.push(i);
    }
    while(!stk.empty())
        stk.pop();
    for(int i=m; i>=1; i--)
    {
        while(!stk.empty()&&v[stk.top()] >= v[i])
            stk.pop();

        if(!stk.empty())
            stdr[i].dr = stk.top();
        else
            stdr[i].dr = m+1;
        stk.push(i);
    }

    int area = 0;
    for(int i=1;i<=m;i++)
        area = max(area,(stdr[i].dr - stdr[i].st - 1) * v[i]);

    return area;

}

int main()
{

    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>s;
        for(int j=0; j<s.size(); j++)
        {
            if(s[j] == '1')
                susjos[i][j+1] = 0;
            else
                susjos[i][j+1] = susjos[i-1][j+1]+1;
        }
    }

    for(int i=n; i>=1; i--)
        for(int j=1; j<=m; j++)
        {
            if(susjos[i][j]==0)
                jossus[i][j] = 0;
            else
            jossus[i][j] = jossus[i+1][j]+1;
        }
    int maxi=0;
    for(int i=1; i<n; i++)
    {
        int maxarie1 = arie(jossus[i+1]);
        int maxarie2 = arie(susjos[i]);
        maxi = max(maxi,maxarie1 + maxarie2);
    }
    cout<<maxi;
    return 0;
}