Cod sursa(job #2150517)

Utilizator cipri321Marin Ciprian cipri321 Data 3 martie 2018 16:51:58
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <stack>
#include <cstring>
#define DIM 201
using namespace std;
ifstream fi("bmatrix.in");
ofstream fo("bmatrix.out");
int n,m;
char A[DIM][DIM],T[DIM][DIM];
int DP[4][DIM];
int rez;
int L[DIM];
stack<int> S;
void init()
{
    memset(L,0,sizeof(L));
    while(!S.empty())
        S.pop();
}
void rotire()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            T[j][n - i + 1] = A[i][j];
    swap(n, m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            A[i][j] = T[i][j];
}
int f(int l)
{
    int rez=0;
    int i=1;
    if(A[l][i]=='0')
        L[i]++;
    else
        L[i]=0;
    while(i<=m)
        if(S.empty()||L[S.top()]<=L[i])
        {
            S.push(i++);
            if(A[l][i]=='0')
                L[i]++;
            else
                L[i]=0;
        }
        else
        {
            int tp=S.top();
            S.pop();
            rez=max(rez,L[tp] * (S.empty() ? (i-1) : i - S.top() - 1));
        }
    while(!S.empty())
    {
        int tp=S.top();
        S.pop();
        rez=max(rez,L[tp] * (S.empty() ? (m-1) : i - S.top() - 1));
    }
    return rez;
}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=n;i++)
        fi>>A[i]+1;
    for(int d=0;d<4;d++)
    {
        init();
        for(int i=1;i<=n;i++)
            DP[d][i]=max(DP[d][i-1],f(i));
        rotire();
    }
    for(int i=1;i<=n;i++)
        rez=max(rez,DP[0][i]+DP[2][n-i]);
    for(int i=1;i<=m;i++)
        rez=max(rez,DP[1][i]+DP[3][m-i]);
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}