ABC160 D - Line++ (400)
単純に全点間の経路を求めると$ O(N^3)
$ x-y間の経路を使う場合と使わない場合について考える
使わない場合の距離は$ j-i
使う場合は$ abs(x-i) + abs(y-j)
それぞれの区間について$ O(1)で求められるので全体で$ O(N^2)で間に合う
問題: https://atcoder.jp/contests/abc160/tasks/abc160_d
提出: https://atcoder.jp/contests/abc160/submissions/11282796
#ABC160 #400pt #D #ABC #AtCoder
#O(N^2)