Cod sursa(job #1821715)

Utilizator lflorin29Florin Laiu lflorin29 Data 3 decembrie 2016 15:08:52
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 200;

void rotate_90(vector<string>&s) {
  vector<string>aux(s[0].size());

  for (int i = 0; i < (int)aux.size(); ++i)
    aux[i].resize(s.size());

  for (int i = 0; i < aux.size(); ++i)
    for (int j = 0; j < aux[i].size(); ++j)
      aux[i][j] = s[j][i];

  s = aux;
}

vector<vector<int>>upp(const vector<string>&s) {
  vector<vector<int>>up(s.size(), vector<int>(s[0].size()));

  for (int i = 0; i < s.size(); ++i)
    for (int j = 0; j < s[i].size(); ++j)
      if (s[i][j] == '1')up[i][j] = 0;
      else {
        up[i][j] = 1;

        if (i != 0)up[i][j] += up[i - 1][j];
      }

  return up;
}
vector<int>solve(vector<string>&s) {
  vector<int>best(s.size());
  vector<vector<int>>ans(s.size(), vector<int>(s[0].size()));
  auto h = upp(s);
  for (int i = 0; i < (int)s.size(); ++i) {
    vector<int>l(s[i].size()), r(s[i].size());
    stack<int>st;

    for (int j = 0; j < (int)s[i].size(); ++j) {
      while (!st.empty() && h[i][st.top()] >= h[i][j])
        st.pop();

      if (!st.empty())
        l[j] = st.top() + 1;
      else l[j] = 0;

      st.push(j);
    }

    st = stack<int>();

    for (int j = s[i].size() - 1; j >= 0; --j) {
      while (!st.empty() && h[i][st.top()] >= h[i][j])
        st.pop();

      if (!st.empty())
        r[j] = st.top() - 1;
      else r[j] = s[i].size() - 1;

      st.push(j);
    }

    for (int j = 0; j < s[i].size(); ++j)
      ans[i][j] = h[i][j] * (r[j] - l[j] + 1);
  }

  for (int i = 0; i < s.size(); ++i) {

    for (int j = 0; j < s[i].size(); ++j)
      best[i] = max(best[i], ans[i][j]);
  }

  return best;
}

void mx_part(vector<int>&v) {
  for (int i = 1; i < v.size(); ++i)v[i] = max(v[i], v[i - 1]);
}

int Get_Ans(vector<string>&s) {
  vector<int>best1 = solve(s);
  mx_part(best1);
  reverse(begin(s), end(s));
  vector<int>best2 = solve(s);
  mx_part(best2);
  reverse(begin(best2), end(best2));
  reverse(begin(s), end(s));
  int ans = 0;

  for (int i = 0; i < s.size() - 1; ++i)
    ans = max(ans, best1[i] + best2[i + 1]);

  return ans;
}

int main() {
  ifstream cin("bmatrix.in");
  ofstream cout("bmatrix.out");
  int n, m;
  cin >> n >> m;
  vector<string>s(n);

  for (int i = 0; i < n; ++i)
    cin >> s[i];
  int ans = Get_Ans(s);

  rotate_90(s);

  ans = max(ans, Get_Ans(s));
  cout << ans;
  return 0;
}