Cod sursa(job #3338897)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 5 februarie 2026 13:32:26
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 1
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("rascoala.in");
    ofstream fout("rascoala.out");
#endif

int n, m, i, j, h[102];
int top, stiv[102];
int inal[102];

bool a[102][102];
char car;

static inline int DAYUM_Plaja(int lst, int ldr, int cst, int cdr) {
    int arie = 0;
    top = 0;
    for(int j = cst; j <= cdr; j++) h[j] = 0;
    for(int i = lst; i <= ldr; i++) {
        for(int j = cst; j <= cdr + 1; j++) {
            if(!a[i][j]) h[j]++;
            else         h[j] = 0;
        
            if(j == cdr + 1) h[j] = 0;
            
            int poz = j;
        while(top && inal[top] >= h[j]) {
            arie = max(arie, inal[top] * (j - stiv[top]));
            poz = stiv[top];
            top--;
        }
        
        if(j != cdr + 1) {
            stiv[++top] = poz;
            inal[top] = h[j];
        }
        }

        
        
        
    }
    return arie;
}

static inline int DAYUM_SplitMat() {
    int arie = 0;
    
    for(int i = 1; i < n; i++) {
        arie = max(arie, DAYUM_Plaja(1, i, 1, m) + DAYUM_Plaja(i + 1, n, 1, m));
    }
    
    for(int j = 1; j < m; j++) {
        arie = max(arie, DAYUM_Plaja(1, n, 1, j) + DAYUM_Plaja(1, n, j + 1, m));
    }
    
    return arie;
}

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
 
    fin >> n >> m;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            fin >> car;
            a[i][j] = car - '0';
        }
    }
    fout << DAYUM_SplitMat();
 
    return 0;
}