解説

f:id:jupiro:20200808015120p:plain

橙のところに注目して解いていきます。

f:id:jupiro:20200808015216p:plain

以下、レベルという概念を導入します。↑の例だとレベルが2, 3, 1みたいな感じです(雰囲気伝われ)

さて、こうすると、 $(h, w)$ がレベル $k$ になる条件を考えると、

であることが必要十分です。

よって右に何個続くかは右からの前計算で、レベルに関しては右上から斜めにと右下から斜めに見ていくことで $O(nm)$ で解くことができました。

提出コード