全国統一プログラミング王決定戦本戦:C - Come Together
問題
解法
各駒の縦方向・横方向の移動は独立に考えられる.
ある x 座標への全ての駒の縦方向の移動量の総和を求めることを考える.ここで,決めた x 座標より小さい座標にある駒の数 cnt_up と座標の値の総和 cost_up を知れれば,決めた x 座標より小さい座標にある駒すべての移動量の総和を求めることが出来る.決めた x 座標より大きい座標にある駒に関しても同様に出来る.これは前計算として累積和を取っておけば O(1) で求めることが出来る.あとは縦方向・横方向それぞれについて最も移動量の総和が小さくて済む座標を見つけ,その総和同士を足し合わせたものが答えとなる.O(H + W + K).
解答
前処理の段階で O(H + W) に出来るところを O(HW) で実装してしまい TLE を出してしまった.