Submission #21284431

---

Source Code Expand

N, K = map(int, input().split())
X, Y = map(int, input().split())
C = [0] * 101010
t = 0
for a in map(int, input().split()):
    C[a] += 1
    t += a

ans = 10 ** 100
cx = 0
for m in range(10 ** 5 + 5, K, -1):
    while C[m]:
        
        # 雑な高速化
        if m - 1 > (t + K - 1) // K and C[m] >= 3:
            cy = max(m if C[m] else m - 1, (t + K - 1) // K)
            ans = min(ans, cx * X + cy * Y)
            d = C[m] - 2
            cx += d
            C[m] -= d
            C[m-K] += d
            t -= K * d
        
        dd = (t + K - 1) // K - (m - 1)
        if dd >= 5 and C[m] >= 3:
            cy = max(m if C[m] else m - 1, (t + K - 1) // K)
            ans = min(ans, cx * X + cy * Y)
            d = min(dd - 3, C[m] - 2)
            cx += d
            C[m] -= d
            C[m-K] += d
            t -= K * d
            
        
        cy = max(m if C[m] else m - 1, (t + K - 1) // K)
        ans = min(ans, cx * X + cy * Y)
        cx += 1
        C[m] -= 1
        C[m-K] += 1
        t -= K
        cy = max(m if C[m] else m - 1, (t + K - 1) // K)
        ans = min(ans, cx * X + cy * Y)
for m in range(K, -1, -1):
    cy = max(m if C[m] else m - 1, (t + K - 1) // K)
    ans = min(ans, cx * X + cy * Y)
    while C[m]:
        cx += 1
        C[m] -= 1
        t -= m
        cy = max(m if C[m] else m - 1, (t + K - 1) // K)
        ans = min(ans, cx * X + cy * Y)
print(ans)

Submission Info

Judge Result