Cod sursa(job #1399840)

Utilizator tudorv96Tudor Varan tudorv96 Data 24 martie 2015 22:33:48
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
using namespace std;

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

const int N = 205;

int z[N][N], n, m, up[N], down[N], sol;
char aux[N][N], a[N][N];

void solve() {
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j)
            z[i][j] = (1 - (a[i][j] - '0')) * (z[i - 1][j] + 1);
        up[i] = down[i] = 0;
    }
    /*for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j)
            fout << z[i][j] << " ";
        fout << "\n";
    }*/
    for (int i = 1; i <= m; ++i)
        for (int j = i; j <= m; ++j) {
            int nw = 0;
            for (int k = 1; k <= n; ++k) {
                if (z[j][k] >= j - i + 1)
                    ++nw;
                else
                    nw = 0;
                up[j]   = max(up[j]  , nw * (j - i + 1));
                down[i] = max(down[i], nw * (j - i + 1));
            }
        }
    for (int i = 2; i <= m; ++i) {
        up[i] = max(up[i], up[i-1]);
        down[m - i + 1] = max(down[m - i + 1], down[m - i + 2]);
    }
    for (int i = 1; i < m; ++i)
        sol = max(sol, up[i] + down[i + 1]);
}

int main() {
    fin >> m >> n;
    for (int i = 1; i <= m; ++i)
        fin >> a[i] + 1;

    solve();

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            aux[j][m - i + 1] = a[i][j];
    swap(m, n);
    for (int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            a[i][j] = aux[i][j];

    solve();

    fout << sol;
}