Cod sursa(job #2764460)

Utilizator marcumihaiMarcu Mihai marcumihai Data 20 iulie 2021 22:31:48
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("bmatrix.in");
ofstream g ("bmatrix.out");
int n, m;
int a[205][205];
int b[205][205];


int dreptunghi(int up, int down, int mt[205][205])
{

    int maxim=0;
    int sum[205][205];
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
            sum[i][j]=0;
    }
    for(int i=up; i<=down; ++i)
    {
        for(int j=1; j<=m; ++j)
            if(mt[i][j]==0)
                sum[i][j]=sum[i-1][j]+1;
    }

    for(int jos=up; jos<=down; ++jos)
    {
        stack <pair<int, int> > stanga;
        stack <pair<int, int> > dreapta;

        int st[1005]= {0};
        int dr[1005]= {0};
        int v[1005]= {0};

        for(int i=1; i<=m; ++i)
            v[i]=sum[jos][i];

        stanga.push({v[1], 1});
        for(int i=2; i<=m; ++i)
        {
            if(v[i]>=stanga.top().first)
            {
                stanga.push({v[i], i});
            }
            else
            {

                while(!stanga.empty() && stanga.top().first>v[i])
                {
                    st[stanga.top().second]=i;
                    stanga.pop();

                }
                stanga.push({v[i], i});
            }
        }
        while(!stanga.empty())
        {
            st[stanga.top().second]=m+1;
            stanga.pop();
        }
        dreapta.push({v[m], m});



        for(int i=m-1; i>0; --i)
        {
            if(v[i]>=dreapta.top().first)
            {
                dreapta.push({v[i], i});
            }
            else
            {

                while(!dreapta.empty() && dreapta.top().first>v[i])
                {
                    dr[dreapta.top().second]=i;
                    dreapta.pop();

                }
                dreapta.push({v[i], i});
            }
        }
        while(!dreapta.empty())
        {
            dr[dreapta.top().second]=0;
            dreapta.pop();
        }
        for(int i=1; i<=m; ++i)
        {

            if(maxim<v[i]*(st[i]-dr[i]-1))
            {
                maxim=v[i]*(st[i]-dr[i]-1);

            }


            maxim=max(maxim, v[i]*(st[i]-dr[i]-1));
        }
    }
    return maxim;
}

int solve(int mt[205][205])
{
    int maxim=0;

    for(int linie=1; linie<n; ++linie)
    {
        int x=dreptunghi(1, linie, mt);
        int y=dreptunghi(linie+1, n, mt);
        maxim=max(maxim, x+y);
    }
    return maxim;
}





int main()
{
    f>>n>>m;
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            char x;
            f>>x;
            a[i][j]=x-'0';
            b[j][i]=x-'0';

        }
    }
    int x=solve(a);
    swap(n, m);
    int y=solve(b);
    g<<max(x, y);
    return 0;
}