Cod sursa(job #3316201)

Utilizator Stefan_25Vicu Stefan Stefan_25 Data 17 octombrie 2025 20:15:16
Problema BMatrix Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.62 kb
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 205;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
int A[Nmax][Nmax], n, m;
char B[Nmax][Nmax];
int v_sus[Nmax][Nmax], s_sus[Nmax], d_sus[Nmax], st_sus[Nmax], dr_sus[Nmax], maxx_sus[Nmax];
int v_jos[Nmax][Nmax], s_jos[Nmax], d_jos[Nmax], st_jos[Nmax], dr_jos[Nmax], maxx_jos[Nmax];
int rez_orizontal;
int v_dreapta[Nmax][Nmax], s_dreapta[Nmax], d_dreapta[Nmax], st_dreapta[Nmax], dr_dreapta[Nmax], maxx_dreapta[Nmax];
int v_stanga[Nmax][Nmax], s_stanga[Nmax], d_stanga[Nmax], st_stanga[Nmax], dr_stanga[Nmax], maxx_stanga[Nmax];
int rez_vertical;
void bordare() {
    for(int i = 1; i <= n; i ++) { /// sus
        for(int j = 1; j <= m; j ++) {
            if(A[i][j] == 0) v_sus[i][j] += v_sus[i-1][j] + 1;
            else v_sus[i][j] = 0;
        }
    }
    for(int i = n; i >= 1; i --) { /// jos
        for(int j = 1; j <= m; j ++) {
            if(A[i][j] == 0) v_jos[i][j] += v_jos[i+1][j] + 1;
            else v_jos[i][j] = 0;
        }
    }
    for(int i = 1; i <= m; i ++) { /// stanga
        for(int j = 1; j <= n; j ++) {
            if(A[j][i] == 0) v_stanga[j][i] += v_stanga[j-1][i] + 1;
            else v_stanga[j][i] = 0;
        }
    }
    for(int i = m; i >= 1; i --) { /// dreapta
        for(int j = 1; j <= n; j ++) {
            if(A[j][i] == 0) v_dreapta[j][i] +=v_dreapta[j+1][i] + 1;
            else v_dreapta[j][i] = 0;
        }
    }
}
void orizontal() {
    for(int i = 1; i <= n + 1; i ++) { /// mergem pe lini
        int k_sus = 0, k_jos = 0;
        /// sus
        for(int j = 1; j <= m; j ++) { /// st
            while(v_sus[i - 1][j] <= v_sus[i - 1][s_sus[k_sus]] && k_sus > 0) {
                k_sus --;
            }
            st_sus[j] = s_sus[k_sus];
            s_sus[++ k_sus] = j;
        }
        k_sus=0;
        for(int j = m; j >= 1; j --) { /// dr
            while(v_sus[i - 1][j] <= v_sus[i - 1][d_sus[k_sus]] && k_sus > 0) {
                k_sus --;
            }
            dr_sus[j] = d_sus[k_sus];
            d_sus[++ k_sus] = j;
        }
        for(int j = 1; j <= m; j ++) {
            if(dr_sus[j] == 0) dr_sus[j] = m + 1;
        }
        for(int j = 1; j <= m; j ++) {
            maxx_sus[i] = max(maxx_sus[i], v_sus[i - 1][j] * (dr_sus[j] - st_sus[j] - 1));
        }
        /// jos
        for(int j = 1; j <= m; j ++) { /// st
            while(v_jos[i][j] <= v_jos[i][s_jos[k_jos]] && k_jos > 0) {
                k_jos --;
            }
            st_jos[j] = s_jos[k_jos];
            s_jos[++ k_jos] = j;
        }
        k_jos=0;
        for(int j = m; j >= 1; j --) { /// dr
            while(v_jos[i][j] <= v_jos[i][d_jos[k_jos]] && k_jos > 0) {
                k_jos --;
            }
            dr_jos[j] = d_jos[k_jos];
            d_jos[++ k_jos] = j;
        }
        for(int j = 1; j <= m; j ++) {
            if(dr_jos[j] == 0) dr_jos[j] = m + 1;
        }
        for(int j = 1; j <= m; j ++) {
            maxx_jos[i] = max(maxx_jos[i], v_jos[i][j] * (dr_jos[j] - st_jos[j] - 1));
        }
    }
    for(int i = 1; i <= n + 1; i ++) {
        maxx_sus[i]=max(maxx_sus[i - 1], maxx_sus[i]);
        rez_orizontal = max(rez_orizontal, maxx_sus[i] + maxx_jos[i]);
    }
}
void vertical() {
    for(int i = 1; i <= m + 1; i ++) { /// mergem pe coloane
        int k_stanga = 0, k_dreapta = 0;
        /// stanga
        for(int j = 1; j <= n; j ++) { /// st
            while(v_stanga[j - 1][i] <= v_stanga[j - 1][s_stanga[k_stanga]] && k_stanga > 0) {
                k_stanga --;
            }
            st_stanga[i] = s_stanga[k_stanga];
            s_stanga[++ k_stanga] = i;
        }
        k_stanga=0;
        for(int j = n; j >= 1; j --) { /// dr
            while(v_stanga[j - 1][i] <= v_stanga[j - 1][d_stanga[k_stanga]] && k_stanga > 0) {
                k_stanga --;
            }
            dr_stanga[i] = d_stanga[k_stanga];
            d_stanga[++ k_stanga] = i;
        }
        for(int j = 1; j <= n; j ++) {
            if(dr_stanga[j] == 0) dr_stanga[j] = n + 1;
        }
        for(int j = 1; j <= n; j ++) {
            maxx_stanga[i] = max(maxx_stanga[i], v_stanga[i - 1][j] * (dr_stanga[j] - st_stanga[j] - 1));
        }
        /// dreapta
        for(int j = 1; j <= n; j ++) { /// st
            while(v_dreapta[i][j] <= v_dreapta[i][s_dreapta[k_dreapta]] && k_dreapta > 0) {
                k_dreapta --;
            }
            st_dreapta[j] = s_dreapta[k_dreapta];
            s_dreapta[++ k_dreapta] = j;
        }
        k_dreapta=0;
        for(int j = n; j >= 1; j --) { /// dr
            while(v_dreapta[i][j] <= v_dreapta[i][d_dreapta[k_dreapta]] && k_dreapta > 0) {
                k_dreapta --;
            }
            dr_dreapta[j] = d_dreapta[k_dreapta];
            d_dreapta[++ k_dreapta] = j;
        }
        for(int j = 1; j <= n; j ++) {
            if(dr_dreapta[j] == 0) dr_dreapta[j] = n + 1;
        }
        for(int j = 1; j <= n; j ++) {
            maxx_dreapta[i] = max(maxx_dreapta[i], v_dreapta[i][j] * (dr_dreapta[j] - st_dreapta[j] - 1));
        }
    }
    for(int i = 1; i <= m + 1; i ++) {
        maxx_stanga[i]=max(maxx_stanga[i - 1], maxx_stanga[i]);
        rez_vertical = max(rez_vertical, maxx_stanga[i] + maxx_dreapta[i]);
    }
}
int32_t main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            fin >> B[i][j];
            A[i][j] = B[i][j] - '0';
        }
    }
    bordare();
    orizontal();
    vertical();
    fout << max(rez_orizontal, rez_vertical);
    return 0;
}