結果

問題 No.3656 Game Scores and Costs
コンテスト
ユーザー sepa38
提出日時 2026-08-27 13:22:05
言語 PyPy3
(7.3.23)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,744 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 242 ms
コンパイル使用メモリ 96,112 KB
実行使用メモリ 310,784 KB
最終ジャッジ日時 2026-08-30 13:04:09
合計ジャッジ時間 8,680 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

"""
[誤答] f(i) が上に凸だと仮定して三分探索する解法

f(i) = S(i) - X*i で、S は「上位 min(K,i) 個の総和」。
S の増分 S(i) - S(i-1) は A の並びに依存して増減するため f は凸ではない。
（K = N のときは S(i) - S(i-1) = A_i そのもので、当然単調ではない）
"""

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, k, x = int(data[0]), int(data[1]), int(data[2])
    a = list(map(int, data[3:3 + n]))

    def f(i):
        # 素直に O(i log i) で計算（三分探索なので呼び出し回数は O(log N)）
        b = sorted(a[:i], reverse=True)
        return sum(b[:min(k, i)]) - x * i

    lo, hi = 1, n
    while hi - lo > 2:  # BUG: f は上に凸ではない
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if f(m1) < f(m2):
            lo = m1 + 1
        else:
            hi = m2 - 1
    print(max(f(i) for i in range(lo, hi + 1)))


main()


# ============================================================
# Hack ケース
# ------------------------------------------------------------
# サンプル: 3問すべて通過する（危険）
#
# 入力:
#   9 2 2
#   10 1 1 1 1 1 1 1 100
#
# 想定解の出力: 92       (f(9) = 110 - 18 = 92)
# この解法の出力: 8      (f(1) = 10 - 2 = 8 付近の局所最大に落ちる)
#
# 理由: 序盤に小さな山を作り、末尾に大きな値を置くと谷を挟んで二峰になる。
#       山と谷の位置を N の 1/3, 2/3 の周辺に置くと三分探索・山登り系が確実に落ちる。
#       N = 2*10^5 で [10^9, 0, 0, ..., 0, 10^9] のような形にすると強力。
# ============================================================
0