Cod sursa(job #2148997)

Utilizator cipri321Marin Ciprian cipri321 Data 2 martie 2018 11:20:51
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <stack>
#include <cstring>
#define DIM 205
using namespace std;
ifstream fi("bmatrix.in");
ofstream fo("bmatrix.out");
int n,m;
char A[DIM][DIM];
int rez;
int L[DIM][DIM];
stack<int> S;
int f(int l1,int c1,int l2,int c2)
{
    memset(L,0,sizeof(L));
    for(int i=l1;i<=l2;i++)
        for(int j=c1;j<=c2;j++)
            if(A[i][j]=='0')
                L[i][j]=L[i-1][j]+1;
    int rez=0;
    for(int l=l1;l<=l2;l++)
    {
        int i=c1;
        while(i<=c2)
            if(S.empty()||L[l][S.top()]<=L[l][i])
                S.push(i++);
            else
            {
                int tp=S.top();
                S.pop();
                rez=max(rez,L[l][tp] * (S.empty() ? (i-c1) : i - S.top() - 1));
            }
        while(!S.empty())
        {
            int tp=S.top();
            S.pop();
            rez=max(rez,L[l][tp] * (S.empty() ? (c2-c1) : i - S.top() - 1));
        }
    }
    return rez;
}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=n;i++)
        fi>>A[i]+1;
    //linie despartire
    for(int i=1;i<n;i++)
        rez=max(rez,f(1,1,i,m)+f(i+1,1,n,m));
    //coloana despartire
    for(int i=1;i<m;i++)
        rez=max(rez,f(1,1,n,i)+f(1,i+1,n,m));
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}