Cod sursa(job #2253940)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 4 octombrie 2018 16:34:41
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstring>

using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");

const int NMAX = 205;

int v[NMAX][NMAX], aux[NMAX][NMAX];
int lineup[NMAX], linedown[NMAX], colup[NMAX], coldown[NMAX];

void solve(int n, int m, int *d) {
    for(int i = 1; i <= n; i ++) {
        vector<int> a(m + 1, 0);
        for(int j = 1; j <= m; j ++) {
            int k = i;
            while(k >= 1 && v[k][j] == 0) {
                a[j] ++;
                k --;
            }
       }
       vector<int> stk(m + 1, 0);
       int sz = 0;
       int maxim = 0;
       stk[++sz] = 0;
       a[0] = INT_MIN;
       for(int j = 1; j <= m; j ++) {
            while(sz > 0 && a[stk[sz]] >= a[j])
                sz --;
            int pretender = (j - stk[sz]) * a[j];
            maxim = max(pretender, maxim);
            stk[++sz] = j;
       }
       d[i] = max(d[i - 1], maxim);
    }
}

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

int main() {
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            char c;
            in >> c;
            v[i][j] = c - '0';
        }
    }

    solve(n, m, lineup);

    rotatematrix(n, m);
    solve(m, n, colup);

    rotatematrix(m, n);
    solve(n, m, linedown);

    rotatematrix(n, m);
    solve(m, n, coldown);

    int ans = 0;
    for(int i = 1; i < n; i ++)
        ans = max(ans, lineup[i] + linedown[n - (i + 1) + 1]);
    for(int i = 1; i < m; i ++)
        ans = max(ans, colup[i] + coldown[m - (i + 1) + 1]);
    out << ans;

    return 0;
}