問題:https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_B
解答:https://onlinejudge.u-aizu.ac.jp/status/users/misora192/submissions/1/DPL_3_B/judge/5013955/C++14
解法:
参考サイト:
ALGORITHM NOTE 長方形探索: 最大長方形の面積 Largest Rectangle
まずはヒストグラム内の最大長方形を求める問題を解く。これはスタックを使ってうまくやる。
https://onlinejudge.u-aizu.ac.jp/status/users/misora192/submissions/1/DPL_3_C/judge/5013937/C++14
その後、各列ごとに上から0が何個連続しているかの2次元配列を作成する。その配列を行ごとにヒストグラムだと思ってみてゆき、そのヒストグラム内の最大長方形を求めればOK。