Cod sursa(job #3315722)

Utilizator Stefan_25Vicu Stefan Stefan_25 Data 15 octombrie 2025 19:26:40
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax = 205;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
int A[Nmax][Nmax];
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];

int32_t main()
{
    int n, m, rez;
    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';
        }
    }
    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 <= n + 1; i ++) { /// mergem pe lini
        int k_sus = 0, k_jos = 0;
        /// sus
        for(int j = 1; j <= m; j ++) { /// stanga
            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 --) { /// dreapta
            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 ++) { /// stanga
            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 --) { /// dreapta
            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 = max(rez, maxx_sus[i] + maxx_jos[i]);
    }
    fout << rez;
    return 0;
}