Cod sursa(job #2468051)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 5 octombrie 2019 12:11:59
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;

const int NMAX=205;
int st[NMAX],dr[NMAX],mat1[NMAX][NMAX],mat2[NMAX][NMAX],s1[NMAX][NMAX],s2[NMAX][NMAX],dp1[NMAX],dp2[NMAX];
int n,m;
stack<pair<int, int>> aux;

int formare(int v[NMAX]){
    ///formam vectorul st
    while(!aux.empty())
        aux.pop();
    st[1]=0;
    aux.push(make_pair(v[1], 1));
    for(int i=2;i<=m;i++){
        while(!aux.empty() && aux.top().first>=v[i])
            aux.pop();
        if(v[i]==v[i-1])
            st[i]=st[i-1]+1;
        else
            if(v[i]>v[i-1])
                st[i]=0;
            else
                if(aux.empty())
                    st[i]=i-1;
                else
                    st[i]=i-aux.top().second-1;
        aux.push(make_pair(v[i], i));
    }
    while(!aux.empty())
        aux.pop();
    ///formam vectorul dr
    dr[m]=0;
    aux.push(make_pair(v[m], m));
    for(int i=m-1;i>0;i--){
        while(!aux.empty() && aux.top().first>=v[i])
            aux.pop();
        if(v[i]==v[i+1])
            dr[i]=dr[i+1]+1;
        else
            if(v[i]>v[i+1])
                dr[i]=0;
        else{
            if(aux.empty())
                dr[i]=m-i;
            else
                dr[i]=aux.top().second-i-1;
        }
        aux.push(make_pair(v[i], i));
    }
    int sum=0;
    for(int i=1;i<=m;i++)
        sum=max(sum, v[i]*(st[i]+dr[i]+1));
    return sum;
}

int rezolvare(int d[NMAX][NMAX]){
    for(int i=1;i<=n;i++)
        dp1[i]=dp2[i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(d[i][j]==0)
                s1[i][j]=1+s1[i-1][j];
            else
                s1[i][j]=0;
    for(int i=n;i>=1;i--)
        for(int j=1;j<=m;j++)
            if(d[i][j]==0)
                s2[i][j]=1+s2[i+1][j];
            else
                s2[i][j]=0;
    for(int i=1;i<=n;i++){
        int x=formare(s1[i]);
        dp1[i]=max(dp1[i-1], x);
    }
    for(int i=n;i>=1;i--){
        int x=formare(s2[i]);
        dp2[i]=max(dp2[i+1], x);
    }
    int sol=0;
    for(int i=1;i<n;i++)
        sol=max(sol, dp1[i]+dp2[i+1]);
    return sol;
}

int main(){
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d%d ", &n, &m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char ch;
            scanf("%c ", &ch);
            mat1[i][j]=ch-'0';
            mat2[j][i]=ch-'0';
        }
    int x1=rezolvare(mat1);
    swap(n, m);
    int x2=rezolvare(mat2);
    printf("%d", max(x1, x2));
    return 0;
}