Cod sursa(job #2689677)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 21 decembrie 2020 20:26:00
Problema BMatrix Scor 44
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.83 kb
#include <iostream>
#include <vector>
#include <cstring>
#include <stdio.h>

using namespace std;

int liniiArie(vector<int> l)
{

    vector <int> stiva;
    vector <int> left(l.size());
    vector <int> right(l.size());
    //right limit
    stiva.push_back(0);
    for(int i=1;i<l.size();i++)
    {
        if(l[i]>=l[stiva[stiva.size()-1]])
        {
            stiva.push_back(i);
        }
        else
        {
            while(!stiva.empty()&&l[i]<l[stiva[stiva.size()-1]])
            {
                right[stiva[stiva.size()-1]]=i;
                stiva.pop_back();
            }
            stiva.push_back(i);
        }
    }
    while(!stiva.empty())
    {
        right[stiva[stiva.size()-1]]=l.size();
        stiva.pop_back();
    }

    stiva.clear();

    //left limit

    stiva.push_back(l.size()-1);
    for(int i=l.size()-2;i>=0;i--)
    {
        if(l[i]>=l[stiva[stiva.size()-1]])
        {
            stiva.push_back(i);
        }
        else
        {
            while(!stiva.empty()&&l[i]<l[stiva[stiva.size()-1]])
            {
                left[stiva[stiva.size()-1]]=i;
                stiva.pop_back();
            }
            stiva.push_back(i);
        }
    }
    while(!stiva.empty())
    {
        left[stiva[stiva.size()-1]]=-1;
        stiva.pop_back();
    }

    int res=0;

    for(int i=0;i<l.size();i++)
    {
        int p=l[i]*(right[i]-left[i]-1);
        if(p>res) res=p;
    }
    return res;
}

int bmatrix(vector<vector<int>> m, int n, int mm)
{
    //a
    vector<int> dmax;
    vector<int> umax;
    vector<int> lmax;
    vector<int> rmax;

    vector<int> lines; //nmax
    //for dmax
    for(int i=0;i<mm;i++) lines.push_back(0);

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<mm;j++)
        {
            if(m[i][j]==0) lines[j]++;
            else lines[j]=0;
        }
        int nr=liniiArie(lines);
        if(i==0) dmax.push_back(nr);
        else dmax.push_back(dmax[dmax.size()-1]>nr?dmax[dmax.size()-1]:nr);
    }
    lines.clear();
    //for umax
    for(int i=0;i<mm;i++) lines.push_back(0);

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<mm;j++)
        {
            if(m[n-1-i][j]==0) lines[j]++;
            else lines[j]=0;
        }
        int nr=liniiArie(lines);
        if(i==0) umax.push_back(nr);
        else umax.push_back(umax[umax.size()-1]>nr?umax[dmax.size()-1]:nr);
    }
    lines.clear();
    //for lmax
    for(int i=0;i<n;i++) lines.push_back(0);

    for(int i=0;i<mm;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(m[j][i]==0) lines[j]++;
            else lines[j]=0;
        }
        int nr=liniiArie(lines);
        if(i==0) lmax.push_back(nr);
        else lmax.push_back(lmax[lmax.size()-1]>nr?lmax[lmax.size()-1]:nr);
    }
    lines.clear();
    //for rmax
    for(int i=0;i<n;i++) lines.push_back(0);

    for(int i=0;i<mm;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(m[j][mm-i-1]==0) lines[j]++;
            else lines[j]=0;
        }
        int nr=liniiArie(lines);
        if(i==0) rmax.push_back(nr);
        else rmax.push_back(rmax[rmax.size()-1]>nr?rmax[rmax.size()-1]:nr);
    }
    lines.clear();

    int mx=0;

    for(int i=0;i<n-1;i++) if(umax[n-2-i]+dmax[i]>mx) {mx=umax[n-2-i]+dmax[i];}
    for(int i=0;i<mm-1;i++) if(rmax[mm-2-i]+lmax[i]>mx) { mx=rmax[mm-2-i]+lmax[i];}

    return mx;
}




int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    int n,m;
    cin>>n>>m;
    vector <vector<int>> mx(n);
    for(int i=0;i<n;i++)
    {
        char s[201];
        cin>>s;
        for(int j=0;j<m;j++)
            if(s[j]=='0') mx[i].push_back(0);
            else mx[i].push_back(1);

    }
    cout<<bmatrix(mx,n,m);
    return 0;
}