D - On AtCoder Conference https://atcoder.jp/contests/abc429/tasks/abc429_d

abc429_d.py

N, M, C = map(int, input().split())
A = list(map(int, input().split()))

# 位置ごとの人数をまとめる
cnt = {}
for a in A:
    if a not in cnt:
        cnt[a] = 0
    cnt[a] += 1

points = sorted(cnt.items())  # (位置, 人数)
K = len(points)

cur = 0
r = 0
ans = 0

for i in range(K):
    while cur < C:
        cur += points[r][1]
        r += 1
        if r >= K:
            r -= K

    if i == 0:
        ans += (M + points[0][0] - points[-1][0]) * cur
    else:
        ans += (points[i][0] - points[i - 1][0]) * cur
    cur -= points[i][1]
print(ans)