Cod sursa(job #1398619)

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

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

const int N = 205;

int st[N], tp = -1, m, n, z[N][N], sol;
char a[N][N];

void add(int x) {
    st[++tp] = x;
}

void pop() {
    --tp;
}

int main() {
    fin >> m >> n;
    fin.get();
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            fin >> a[i][j];
    for (int k = 1; k < m; ++k) { //linie delimitatoare
        int sol1 = 0, sol2 = 0;
        for (int j = 1; j <= n; ++j)
            z[k][j] = (a[k][j] == '0') ? (z[k - 1][j] + 1) : 0;

        for (int j = 1; j <= n; ++j)
            z[k + 1][j] = (a[k + 1][j] == '0');

        for (int i = k + 2; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                z[i][j] = (a[i][j] == '0') ? (z[i - 1][j] + 1) : 0;

        for (int i = 1; i <= m; ++i) {
            tp = -1;
            for (int j = 1; j <= n; ++j) {
                if (tp != -1 && z[i][st[tp]] > z[i][j])
                    pop();
                if (tp == -1 || z[i][st[tp]] < z[i][j])
                    add(j);
                if (tp != -1) {
                    if (i <= k)
                        sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
                    else
                        sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
                }
            }
            tp = -1;
            for (int j = n; j; --j) {
                if (tp != -1 && z[i][st[tp]] > z[i][j])
                    pop();
                if (tp == -1 || z[i][st[tp]] < z[i][j])
                    add(j);
                if (tp != -1) {
                    if (i <= k)
                        sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
                    else
                        sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
                }
            }
        }
        sol = max(sol, sol1 + sol2);
    }
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            z[i][j] = (a[i][j] == '0') ? (z[i - 1][j] + 1) : 0;

    for (int k = 1; k < n; ++k) {// coloana delimitatoare
        int sol1 = 0, sol2 = 0;
        for (int i = 1; i <= m; ++i) {
            tp = -1;
            for (int j = 1; j <= n; ++j) {
                if (j == k + 1)
                    tp = -1;
                if (tp != -1 && z[i][st[tp]] > z[i][j])
                    pop();
                if (tp == -1 || z[i][st[tp]] < z[i][j])
                    add(j);
                if (tp != -1) {
                    if (j <= k)
                        sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
                    else
                        sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
                }
            }
            tp = -1;
            for (int j = n; j; --j) {
                if (j == k)
                    tp = -1;
                if (tp != -1 && z[i][st[tp]] > z[i][j])
                    pop();
                if (tp == -1 || z[i][st[tp]] < z[i][j])
                    add(j);
                if (tp != -1) {
                    if (j <= k)
                        sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
                    else
                        sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
                }
            }
        }
        sol = max(sol, sol1 + sol2);
    }
    fout << sol;
}