Cod sursa(job #1823472)

Utilizator greenadexIulia Harasim greenadex Data 6 decembrie 2016 13:45:40
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair

using namespace std;

const string name = "bmatrix",
             in_file = name + ".in",
             out_file = name + ".out";

ifstream fin(in_file);
ofstream fout(out_file);

const int MAX = 205;

int n, m;
int matrix[MAX][MAX];
int heights[MAX][MAX];
int lefty[MAX], righty[MAX];
int aux[MAX][MAX];
vector<int> stackk;
int dp0[MAX], dp90[MAX], dp180[MAX], dp270[MAX];
//dp[i] = largest submatrix full of 0s above line i

void rotate(int n, int m) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            aux[j][n - i + 1] = matrix[i][j];
        }
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            matrix[i][j] = aux[i][j];
        }
    }
}

void build_heights(int n, int m) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!matrix[i][j]) {
                heights[i][j] = heights[i - 1][j] + 1;
            } else {
                heights[i][j] = 0;
            }
        }
    }
}

void compute(int n, int m, int dp[]) {
    build_heights(n, m);
    for (int i = 1; i < n; i++) {
        stackk.clear();
        stackk.push_back(0);
        heights[i][0] = -1;

        for (int j = 1; j <= m; j++) {
            int height = heights[i][j];

            while (!stackk.empty() && heights[i][stackk.back()] >= height) {
                stackk.pop_back();
            }

            lefty[j] = stackk.back();
            stackk.push_back(j);
        }

        stackk.clear();
        stackk.push_back(m + 1);
        heights[i][m + 1] = -1;

        for (int j = m; j > 0; j--) {
            int height = heights[i][j];

            while (!stackk.empty() && heights[i][stackk.back()] >= height) {
                stackk.pop_back();
            }

            righty[j] = stackk.back();
            stackk.push_back(j);
        }

        dp[i] = dp[i - 1];
        for (int j = 1; j <= m; j++) {
            dp[i] = max(dp[i], heights[i][j] * (righty[j] - lefty[j] - 1));
        }
    }
}

int main() {
    fin >> n >> m;

    string str;
    for (int i = 1; i <= n; i++) {
        fin >> str;
        for (int j = 1; j <= m; j++) {
            matrix[i][j] = str[j - 1] - '0';
        }
    }

    compute(n, m, dp0);
    rotate(n, m);
    compute(m, n, dp90);
    rotate(m, n);
    compute(n, m, dp180);
    rotate(n, m);
    compute(m, n, dp270);

    int result = 0;
    for (int i = 1; i < n; i++) {
        result = max(result, dp0[i] + dp180[n - i]);
    }

    for (int i = 1; i < m; i++) {
        result = max(result, dp90[i] + dp270[m - i]);
    }

    fout << result;
    return 0;
}