結果

問題 No.1071 ベホマラー
コンテスト
ユーザー Kohei
提出日時 2026-06-21 21:24:13
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 128 ms / 2,000 ms
コード長 653 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 468 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 101,248 KB
最終ジャッジ日時 2026-06-21 21:24:23
合計ジャッジ時間 3,127 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N, K, X, Y = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(lambda x: ((x - 1) + (K - 1))//K, A))
maxB = max(B)
if X > Y:
    exit(print(maxB))

# 三分探索
def f(x): # ベホマラーをx回使うときの全体コスト
    cnt = 0
    for b in B:
        if b > x:
            cnt += b - x
    return x*Y + cnt*X

left = 0
right = maxB

while right - left > 5:
    m1 = (left * 2 + right)//3
    m2 = (left + right * 2)//3

    if f(m1) > f(m2):
        # left ~ m1 間には存在しない
        left = m1
    else:
        right = m2

ans = 1e18
for i in range(left, right + 1):
    ans = min(ans, f(i))
print(ans)
0