Cod sursa(job #2134332)

Utilizator cella.florescuCella Florescu cella.florescu Data 17 februarie 2018 20:51:42
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e2;

int mat[MAXN + 2][MAXN + 2], aux[MAXN + 2][MAXN + 2], dp[4][MAXN + 2], num[MAXN + 2], n, m;
pair <int, int> stk[MAXN];

inline void solve(int n, int m, int wh) {
  memset(num, 0, sizeof num);
  for (int i = 1; i <= n; ++i) {
    int st = -1;
    mat[i][m + 1] = 0;
    for (int j = 1; j <= m + 1; ++j) {
      num[j] = mat[i][j] * (num[j] + 1);
      int len = 0;
      while (st >= 0 && stk[st].first >= num[j]) {
        len += stk[st--].second;
        dp[wh][i] = max(dp[wh][i], len * stk[st + 1].first);
      }
      stk[++st] = {num[j], len + 1};
    }
  }
}

inline void roootate(int& n, int& m) {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      aux[i][j] = mat[i][j];
  for (int i = m; i > 0; --i)
    for (int j = 1; j <= n; ++j)
      mat[m - i + 1][j] = aux[j][i];
  swap(n, m);
}

int main()
{
    ifstream fin("bmatrix.in");
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
      string s;
      fin >> s;
      for (int j = 1; j <= m; ++j)
        mat[i][j] = '1' - s[j - 1];
    }
    fin.close();
    for (int i = 0; i < 4; ++i) {
      solve(n, m, i);
      roootate(n, m);
    }
    int ans = 0;
    for (int i = 1; i < n; ++i)
      ans = max(ans, dp[0][i] + dp[2][n - i]);
    for (int i = 1; i < m; ++i)
      ans = max(ans, dp[1][i] + dp[3][m - i]);
    ofstream fout("bmatrix.out");
    fout << ans;
    fout.close();
    return 0;
}