Cod sursa(job #1983183)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 21 mai 2017 14:03:03
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <string>
#include <cstring>

using namespace std;

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

const int nmax = 200 + 5;
const int inf = 1 << 30;

int n, m;
bool v[nmax + 1][nmax + 1];
int h[nmax + 1];
pair<int, int> st[nmax + 1];

int sol[ 4 ][nmax + 1];
bool aux[nmax + 1][nmax + 1];

string s;

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

    swap(n, m);
    memcpy(v, aux, sizeof(v));
}

void solve (int ind) {
    memset(h, 0, sizeof(h));

    for (int i = 1; i <= n; ++ i) {
        int top = 0;

        sol[ ind ][ i ] = sol[ ind ][i - 1];

        for (int j = 1; j <= m + 1; ++ j) {
            if (v[ i ][ j ] == 0 && j <= m) ++ h[ j ];
            else                  h[ j ] = 0;

            int s = 0;
            while (top > 0 && st[ top ].first >= h[ j ]) {
                s += st[ top ].second;
                sol[ ind ][ i ] = max(sol[ ind ][ i ], s * st[ top ].first);
                -- top;
            }

            st[ ++ top ] = make_pair(h[ j ], s + 1);
        }
    }
}

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

    for (int i = 1; i <= n; ++ i) {
        fin >> s;

        for (int j = 1; j <= m; ++ j) {
            v[ i ][ j ] = s[j - 1] - '0';
        }
    }

    for (int i = 0; i < 4; ++ i) {
        solve( i );
        rotate_90();
    }

    int ans = 0;
    for (int i = 1; i < n; ++ i) {
        ans = max(ans, sol[ 0 ][ i ] + sol[ 2 ][n - i]);
    }

    for (int i = 1; i < m; ++ i) {
        ans = max(ans, sol[ 1 ][ i ] + sol[ 3 ][m - i]);
    }

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}