540,541

540

あみだくじ。あらかじめすべての横棒について、番号iの縦棒と番号jの縦棒をswapするかを計算しておいて、横棒を消さない場合の合計点数、横棒kを消した場合swapした後の合計点数をすべて調べて最小の合計点数を返した。

541

Nが大きいので、普通にシミュレーションするとTLE。東と南が通るたびに入れ替わるので、dpでN-1回目での各交差点を通った回数を計算。東と南が決まるのでそれでN回目を計算する。
N-1回目の時、(i,j)の交差点の通過回数をa回とすると、aが偶数なら{東へa/2回、南へa/2回}行く、aが奇数の場合、最初が東なら{東へ(a+1)/2回、南へ(a-1)/2回}行き、最初が南なら{東へ(a-1)/2回、南へ(a-1)/2回}行く、というのを(i+1,j)と(i,j+1)に加算していく。