Cod sursa(job #1398595)

Utilizator tudorv96Tudor Varan tudorv96 Data 24 martie 2015 12:18:53
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.47 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 i = 1; i <= k; ++i)
            for (int j = 1; j <= n; ++j)
                z[i][j] = (a[i][j] == '0') ? (z[i - 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;
        /*fout << k << "===\n";

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j)
                fout << z[i][j] << " ";
            if (i == k)
                fout << "\n";
            fout << "\n";
        }
        fout << "\n";*/

        for (int i = 1; i <= k; ++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)
                    sol1 = max(sol1, (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)
                    sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
            }
        }
        for (int i = k + 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)
                    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)
                    sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
            }
        }
        sol = max(sol, sol1 + sol2);
        //fout << "linia " << k << " " << sol1 << " " << sol2 << "\n";
    }
    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 <= k; ++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)
                    sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
            }
            tp = -1;
            for (int j = k; 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)
                    sol1 = max(sol1, (j - st[tp] + 1) * z[i][st[tp]]);
            }
            tp = -1;
            for (int j = k + 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)
                    sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
            }
            tp = -1;
            for (int j = n; j != k; --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)
                    sol2 = max(sol2, (j - st[tp] + 1) * z[i][st[tp]]);
            }
        }
        sol = max(sol, sol1 + sol2);
    }
    fout << sol;
}