Cod sursa(job #3352948)

Utilizator Maya_PopaPopa Maya Diana Maya_Popa Data 2 mai 2026 21:43:40
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 201

using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int m,n;
int mat[MAX][MAX];
int h[MAX];
int area(int n, int h[]) {
    stack<int> s;
    int maxim=0;
    vector<int> cop(n+2, 0);
    for(int i=1; i<=n; i++) {
        cop[i]=h[i];
    }
    for (int i=0; i<=n+1; i++) {
        while (!s.empty() && cop[s.top()]>cop[i]) {
            int lung=cop[s.top()];
            s.pop();
            int lat=i-s.top()-1;
            maxim = max(maxim, lung*lat);
        }
        s.push(i);
    }
    return maxim;
}
int main() {
    int i,j,maxim;
    fin>>m>>n;
    for (i=1; i<=m; i++) {
        string s;
        fin>>s;
        for (j=1; j<=n; j++) {
            mat[i][j]=s[j-1]-'0';
        }
    }
    vector<int> up(m+2, 0), down(m+2, 0), st(n+2, 0), dr(n+2, 0);
    for (i=1; i<=m; i++) {
        for (j=1; j<=n; j++) {
            if (mat[i][j]==0) {
                h[j]++;
            } else {
                h[j]=0;
            }
        }
        up[i]=max(up[i-1], area(n, h));
    }
    for (j=1; j<=MAX; j++) {
        h[j]=0;
    }
    for (i=m; i>=1; i--) {
        for (j=1; j<=n; j++) {
            if (mat[i][j]==0) {
                h[j]++;
            } else {
                h[j]=0;
            }
        }
        down[i]=max(down[i+1], area(n, h));
    }
    maxim=0;
    for (i=1; i<m; i++) {
        maxim=max(maxim, up[i]+down[i+1]);
    }
    for (j=1; j<=MAX; j++) {
        h[j]=0;
    }
    for (j=1; j<=n; j++) {
        for (i=1; i<=m; i++) {
            if (mat[i][j]==0) {
                h[i]++;
            } else {
                h[i]=0;
            }
        }
        st[j]=max(st[j-1], area(m, h));
    }
    for (j=1; j<=MAX; j++) {
        h[j]=0;
    }
    for (j=n; j>=1; j--) {
        for (i=1; i<=m; i++) {
            if (mat[i][j]==0) {
                h[i]++;
            } else {
                h[i]=0;
            }
        }
        dr[j]=max(dr[j+1], area(m, h));
    }
    for (j=1; j<n; j++) {
        maxim=max(maxim, st[j]+dr[j+1]);
    }
    fout<<maxim<<endl;
    return 0;
}