Cod sursa(job #3338874)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 5 februarie 2026 12:47:00
Problema BMatrix Scor 48
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, i, j, h[202];
int st[202], dr[202];
int top, stiv[202];

bool a[202][202];
char car;

static inline int DAYUM_Skyline(int cst, int cdr) {
    memset(st, 0, sizeof(st));
    memset(dr, 0, sizeof(dr));
    
    stiv[top = 0] = cst - 1;
    for(int j = cst; j <= cdr; j++) {
        while(top && h[stiv[top]] >= h[j]) top--;
        st[j] = stiv[top];
        stiv[++top] = j;
    }
    
    stiv[top = 0] = cdr + 1;
    for(int j = cdr; j >= cst; j--) {
        while(top && h[stiv[top]] >= h[j]) top--;
        dr[j] = stiv[top];
        stiv[++top] = j;
    }
    
    int arie = 0;
    for(int j = cst; j <= cdr; j++) {
        arie = max(arie, h[j] * (dr[j] - st[j] - 1));
    }
    
    /*for(int j = cst; j <= cdr; j++) cout << st[j] << " ";
    cout << "\n";
    for(int j = cdr; j >= cst; j--) cout << dr[j] << " ";
    cout << "\n\n";*/
    
    return arie;
}

static inline int DAYUM_Plaja(int lst, int ldr, int cst, int cdr) {
    int arie = 0;
    for(int i = lst; i <= ldr; i++) {
        for(int j = cst; j <= cdr; j++) h[j] = 0;
        for(int ii = i; ii <= ldr; ii++) {
            for(int j = cst; j <= cdr; j++) {
                if(!a[ii][j]) h[j]++;
                else          h[j] = 0;
            }
            arie = max(arie, DAYUM_Skyline(cst, cdr));
        }
    }
    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;
}