atcoder.jp素朴に配るDPを実装するとになりTLEとなる(なってしまった....)。 例えば下記の入力だと遷移数がマス目の長さと同じオーダになるので通らない。 200000 1 1 200000 こういう時は累積和でdpを高速化するのが定番らしい。解説動画が非常に分かりやす…