test/aoj/DPL_3_B/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B
• Link: View error logs on GitHub Actions

Depends on

• Input vector (Mylib/IO/input_vector.cpp)
• Largest rectangle (Mylib/Typical/max_rectangle.cpp)
• Largest rectangle in histogram (Mylib/Typical/max_rectangle_in_histogram.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B"

#include <iostream>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/Typical/max_rectangle.cpp"

namespace hl = haar_lib;

int main() {
  int H, W;
  std::cin >> H >> W;

  auto c = hl::input_vector<int>(H, W);

  auto ans = hl::max_rectangle(c, 0);
  std::cout << ans << std::endl;

  return 0;
}

#line 1 "test/aoj/DPL_3_B/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B"

#include <iostream>
#include <vector>
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 2 "Mylib/Typical/max_rectangle.cpp"
#include <algorithm>
#line 2 "Mylib/Typical/max_rectangle_in_histogram.cpp"
#include <stack>
#include <utility>
#line 5 "Mylib/Typical/max_rectangle_in_histogram.cpp"

namespace haar_lib {
  template <typename T>
  T max_rectangle_in_histogram(const std::vector<T> &h) {
    std::stack<std::pair<T, int>> st;
    T ret = 0;

    for (size_t i = 0; i < h.size(); ++i) {
      if (st.empty()) {
        st.emplace(h[i], i);
      } else if (st.top().first < h[i]) {
        st.emplace(h[i], i);
      } else if (st.top().first > h[i]) {
        int j = i;
        while (not st.empty() and st.top().first > h[i]) {
          ret = std::max(ret, st.top().first * ((T) i - st.top().second));
          j   = st.top().second;
          st.pop();
        }
        st.emplace(h[i], j);
      }
    }

    while (not st.empty()) {
      ret = std::max(ret, st.top().first * ((T) h.size() - st.top().second));
      st.pop();
    }

    return ret;
  }
}  // namespace haar_lib
#line 5 "Mylib/Typical/max_rectangle.cpp"

namespace haar_lib {
  template <typename T>
  int max_rectangle(const std::vector<std::vector<T>> &d, T value) {
    const int H = d.size();
    const int W = d[0].size();

    std::vector<std::vector<int>> c(H, std::vector<int>(W));
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (d[i][j] == value) c[i][j] = 1;
      }
    }

    for (int i = 1; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (c[i][j]) {
          c[i][j] += c[i - 1][j];
        }
      }
    }

    int ret = 0;
    for (int i = 0; i < H; ++i) {
      int t = max_rectangle_in_histogram<int>(c[i]);
      ret   = std::max(ret, t);
    }

    return ret;
  }
}  // namespace haar_lib
#line 7 "test/aoj/DPL_3_B/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int H, W;
  std::cin >> H >> W;

  auto c = hl::input_vector<int>(H, W);

  auto ans = hl::max_rectangle(c, 0);
  std::cout << ans << std::endl;

  return 0;
}

Back to top page