Cod sursa(job #3347780)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 18 martie 2026 12:19:22
Problema BMatrix Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.33 kb
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 205;

int matrix[NMAX][NMAX];
int heights_up_down[NMAX][NMAX], heights_down_up[NMAX][NMAX];
int max_up_down[NMAX], max_down_up[NMAX], next_left[NMAX], next_right[NMAX];

void transposition_matrix(int &n, int &m, int a[NMAX][NMAX]) {
    int b[NMAX][NMAX];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            b[j][i] = a[i][j];

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = b[i][j];
    swap(n, m);
}

void compute_heights(int n, int m) {
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (matrix[i][j] == 1)
                heights_up_down[i][j] = 0;
            else
                heights_up_down[i][j] = heights_up_down[i - 1][j] + 1;
        }
    }
    for (int j = m; j >= 1; j--) {
        for (int i = n; i >= 1; i--) {
            if (matrix[i][j] == 1)
                heights_down_up[i][j] = 0;
            else
                heights_down_up[i][j] = heights_down_up[i + 1][j] + 1;
        }
    }
}
void compute_left(int n, const int v[NMAX]){
    stack<int> st;
    for(int i = 1; i <= n; i++){
        while(!st.empty() && v[st.top()] >= v[i]){
            st.pop();
        }
        if(st.empty()) next_left[i] = 0;
        else next_left[i] = st.top();
        st.push(i);
    }
}
void compute_right(int n, const int v[NMAX]){
    stack<int> st;
    for(int i = n; i >= 1; i--){
        while(!st.empty() && v[st.top()] >= v[i]){
            st.pop();
        }
        if(st.empty()) next_right[i] = n + 1;
        else next_right[i] = st.top();
        st.push(i);
    }
}
void compute_max_rectangle(int n, int m, int a[NMAX][NMAX], int result[NMAX]) {
    for (int i = 1; i <= n; i++)
        result[i] = 0;
    for (int i = 1; i <= n; i++) {
        compute_left(m, a[i]);
        compute_right(m, a[i]);
        for (int j = 1; j <= m; j++) {
            result[i] = max(result[i], a[i][j] * (next_right[j] - next_left[j] - 1));
        }
    }
}
void compute_result(int n, int m) {
    compute_heights(n, m);
    compute_max_rectangle(n, m, heights_up_down, max_up_down);
    compute_max_rectangle(n, m, heights_down_up, max_down_up);
    int result = 0;
    for (int i = 1; i <= n; i++) {
        int up_son = max_up_down[i];
        int down_son = max_down_up[i + 1];
        result = max(result, up_son + down_son);
        up_son = max_up_down[i - 1];
        down_son = max_down_up[i];
        result = max(result, up_son + down_son);
    }
    transposition_matrix(n, m, matrix);
    compute_heights(n, m);
    compute_max_rectangle(n, m, heights_up_down, max_up_down);
    compute_max_rectangle(n, m, heights_down_up, max_down_up);
    for (int i = 1; i <= n; i++) {
        int up_son = max_up_down[i];
        int down_son = max_down_up[i + 1];
        result = max(result, up_son + down_son);
        up_son = max_up_down[i - 1];
        down_son = max_down_up[i];
        result = max(result, up_son + down_son);
    }
    printf("%d", result);
}
char line[NMAX];
int main() {
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);

    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {

        scanf("%s", &line);
        for (int j = 0; j < m; j++)
            matrix[i][j + 1] = line[j] - '0';
    }
    compute_result(n, m);
    return 0;
}