Cod sursa(job #3136862)

Utilizator profinfo114Prof Info profinfo114 Data 8 iunie 2023 23:38:05
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

int n, m, up[205], down[205], dp[205][205], maxim;
bool temp[205][205], v[205][205];

void rotire(int n, int m) {
    for(int j = 1; j <= m; j++) {
        for(int i = 1; i <= n; i++) {
            temp[j][i] = v[n - i + 1][j];
        }
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            v[i][j] = temp[i][j];
        }
    }
}

void dinamica(int n, int m) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j] + v[i][j];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int last = 0;
            for(int k = 1; k <= m; k++) {
                if(dp[j][k] - dp[i - 1][k] != 0) {
                    int len = (j - i + 1) * (k - last - 1);
                    up[j] = max(up[j], len);
                    down[i] = max(down[i], len);
                    last = k;
                }
            }
            int len = (j - i + 1) * (m - last);
            up[j] = max(up[j], len);
            down[i] = max(down[i], len);
        }
    }
    for(int i = 1; i <= n; i++) {
        up[i] = max(up[i], up[i - 1]);
    }
    for(int i = n; i >= 1; i--) {
        down[i] = max(down[i], down[i + 1]);
    }
    for(int i = 1; i <= n; i++) {
        maxim = max(maxim, up[i] + down[i + 1]);
    }
}

int main() {
    fin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c;
            fin >> c;
            v[i][j] = (c == '1');
        }
    }
    dinamica(n, m);
    rotire(n, m);
    for(int i = 1; i <= n; i++) {
        up[i] = down[i] = 0;
    }
    dinamica(m, n);
    fout << maxim;
    return 0;
}