ABC129 D - Lamp - ツバサの備忘録

解法

$O(N^{2})$ が間に合うので、 $(i,j)$ に設置した際に照らすことができるマスの個数が $O(1)$ で求まれば、全探索をしつつ最大値を求めることでこの問題に答えることができます。
ということで、前計算をします。
まず、縦に伸びる光と横に伸びる光は無関係のため、独立に考えることができます。
今回は、横に伸びる方について考えていきます。
$i$ 行目について考えると、左端のマスから順にみていき、
$j$ 列目、つまり $s_{ij}$ に障害物がない場合、そこから右側に連続して障害物がない場所の個数を調べ、調べた箇所に対して、その個数をメモする、という操作を行うことで、横方向で照らすことのできるマスの個数がわかります。
同様のことを縦方向についても行うことで、 $s_{ij}$ に明かりを設置した結果、照らすことのできるマスの個数が以下のようにして求められます。