概要

各料理を「選ぶ / 選ばない」の 2 通りで考えると、全組み合わせは最大でも \(2^{19}\) 通りです。
この全探索を行い、各組み合わせについて満足度 \( \sum A_i - D \times \max(0, \sum B_i - K)\) を計算して最大値を取れば解けます。

考察

この問題は、料理ごとに「注文するかしないか」を決める問題です。
つまり、部分集合最適化になっています。

• 料理数 \(N \le 19\) と小さい
• 各料理は高々 1 回しか選べない
• 組み合わせごとの評価式はそのまま計算できる

という条件から、全ての部分集合を試す方針が自然です。

なぜ全探索で間に合うか

全組み合わせ数は \(2^N\) 通りで、最大でも \(2^{19} = 524{,}288\) 通りです。
1 通りごとに選んだ料理の合計おいしさ・合計こってり度を計算しても、十分高速です。

素朴法の懸念と解決

「全探索は重そう」と感じるかもしれませんが、制約が小さいため TLE にはなりません。
一方で、貪欲（例：おいしさが高い順に選ぶ）では、ペナルティが後から効いて最適を逃す可能性があり WA になります。
よって、この制約では正確な全探索が最も確実です。

アルゴリズム

1. 入力を受け取る（\(A_i, B_i\)）。
2. 答え ans を 0 で初期化（何も注文しないケース）。
3. mask を \(0\) から \((1<<N)-1\) まで動かし、部分集合を表す。
   • mask の立っているビットに対応する料理を選んだとみなす。
   • 合計おいしさ sum_a、合計こってり度 sum_b を計算。
4. 満足度を計算：
   • \(sum_b \le K\) なら score = sum_a
   • \(sum_b > K\) なら score = sum_a - D \times (sum_b - K)
5. ans = max(ans, score) で更新。
6. 最後に ans を出力。

ビット全探索のイメージ

例えば \(N=3\) なら、mask=5 (101_2) は
- 0 番目の料理：選ぶ
- 1 番目の料理：選ばない
- 2 番目の料理：選ぶ
を表します。

計算量

• 時間計算量: \(O(N \cdot 2^N)\)
• 空間計算量: \(O(N)\)（入力配列を除けば定数）

実装のポイント

• 初期値 ans = 0 にしておくと、「何も選ばない」ケースを自然に含められます。

• ペナルティは 超過分だけ なので、sum_b > K のときだけ引きます。

• Python でも \(N \le 19\) ならこの全探索で十分間に合います。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K, D = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    ans = 0  # 何も選ばない場合

    for mask in range(1 << N):
        sum_a = 0
        sum_b = 0
        m = mask
        i = 0
        while m:
            if m & 1:
                sum_a += A[i]
                sum_b += B[i]
            i += 1
            m >>= 1
        # m が 0 でも i 未満のビットしか見ていないが、それで十分
        if sum_b > K:
            score = sum_a - D * (sum_b - K)
        else:
            score = sum_a
        if score > ans:
            ans = score

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。