Cod sursa(job #3268832)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 17 ianuarie 2025 18:51:03
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int inf = 1e7 + 2;
int n, m, i, j, h[202], rasp;
int lLat[2][202], lInal[2][202];
bool a[202][202];

static inline void CalcMat1() {
    memset(h, 0, sizeof(h));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j]) h[j]++;
            else h[j] = 0;

            int ma = 0;
            int mi = inf;
            for(int k = j; k >= 1; k--) {
                mi = min(mi, h[k]);
                ma = max(ma, mi * (j - k + 1));
            }

             lLat[0][i] = max( lLat[0][i], max( lLat[0][i - 1], ma));
            lInal[0][j] = max(lInal[0][j], max(lInal[0][j - 1], ma));
        }
    }
}

static inline void CalcMat2() {
    memset(h, 0, sizeof(h));
    for(int i = n; i >= 1; i--) {
        for(int j = m; j >= 1; j--) {
            if(a[i][j]) h[j]++;
            else h[j] = 0;

            int ma = 0;
            int mi = inf;
            for(int k = j; k <= m; k++) {
                mi = min(mi, h[k]);
                ma = max(ma, mi * (k - j + 1));
            }

             lLat[1][i] = max( lLat[1][i], max( lLat[1][i + 1], ma));
            lInal[1][j] = max(lInal[1][j], max(lInal[1][j + 1], ma));
        }
    }
}

int main() {
    fin >> n >> m;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            char c;
            fin >> c;
            if(c == '0') a[i][j] = true;
        }
    }

    CalcMat1();
    CalcMat2();

    for(i = 1; i < n; i++) rasp = max(rasp,  lLat[0][i] +  lLat[1][i + 1]);
    for(j = 1; j < m; j++) rasp = max(rasp, lInal[0][j] + lInal[1][j + 1]);
    fout << rasp;

    return 0;
}