ABC147 E - Balanced Path (500)
本番の考察
あるマスでの偏りの最大値は$ H \times W \times 80で全体で$ O(H^2W^2)、定数倍が大きくてTLE
もっと改善する方法が思いつかず終了
終了後の考察
あるマスでの偏りの最大値は$ (H + W) \times 80で全体で$ O(HW(H+W))
定数倍が80でも間に合う
$ dp[i][j][偏りがk] として右と下方向にメモ化しながらDFSしていけば良い
最終的に$ dp[h-1][w-1][k] でtrueとなる中でkの絶対値が最小のが答え
上のDPをmapにするとTLEしたので配列で持ったところAC