ABC216 E - Amusement Park
https://atcoder.jp/contests/abc216/tasks/abc216_e
解説
その時点で楽しさの最も高いアトラクションに乗り続ければよいのは明らかです。 以下、Aは大きい順にソートされているとします。
最初に乗るアトラクションはA[0]ですが、A[0]にいつまで乗り続けられるかというと、 A[0]とA[1]が等しくなるまで、すなわちA[0]-A[1]回です。
A[0]とA[1]が等しくなると、今度はこれらの値がA[2]に等しくなるまで 2つのアトラクションに乗り続けることになります。 アトラクションに乗る回数は (A[1]-A[2]) * 2 回です。
同様に、i=0, 1, 2, ... として 初期値A[i]のアトラクションの楽しさがA[i+1]になるまでA[i]-A[i+1]回乗る×(i+1)台として、 この回数の合計がKに達するまでアトラクションに乗ることを考えればよいです。 （回数がKに達する前に全てのアトラクションの楽しさが0になったらその時点で終了します。Aの末尾に番兵として0を加えると楽）
あるアトラクションの楽しさがxからyに変化したとき、この間に獲得した満足度はx+(x-1)+...+(y+1)ですので、 上記のそれぞれのiについてこの満足度を足していけば答えになります。
コンテスト中に提出した解答はこちらです。
