Cod sursa(job #3184799)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 16 decembrie 2023 21:01:28
Problema BMatrix Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int inf = 1e9;
int n, m, i, j, k, r, fr[202];
int sus[202], jos[202];
int dr[202], st[202], mi, ma;
bool a[202][202];

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

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

             st[i] = max( st[i], max( st[i - 1], ma));
            sus[j] = max(sus[j], max(sus[j - 1], ma));
        }
    }
}

static inline void calc2() {
    for(i = n; i >= 1; i--) {
        for(j = m; j >= 1; j--) {
            if(a[i][j]) fr[j]++;
            else        fr[j] = 0;

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

             dr[i] = max( dr[i], max( dr[i + 1], ma));
            jos[j] = max(jos[j], max(jos[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;
        }
    }

    calc1();
    calc2();

    for(i = 1; i < n; i++) r = max(r,  st[i] +  dr[i + 1]);
    for(j = 1; j < m; j++) r = max(r, sus[j] + sus[j + 1]);
    fout << r;

    return 0;
}