POJ 2566は，そのままだとしゃくとりできないが，累積和にしてソートするとしゃくとりできるようになる．なぜならば，問題が知りたいのは合計の絶対値であるから，累積和の差だけを考えればよいため．カンニング先→POJ-2566 : Bound Found - komiyamの日記 P…

概要 N個の提灯が下がった糸を垂らす．片方の端点はAとし，他方をBとする． このとき，糸は重力にしたがって垂れ下がる． i番目の提灯の高さをH_iとすると， H_1 = A, H_N = B, H_i = (H_(i-1) + H_(i+1)) - 1 が成り立つ． あるAが与えられたとき，全ての提…