概要

各お菓子の基本ポイント \(T_i\) と補正値 \(C_i\) の和を満足度とし、最も高い上位 \(K\) 個を選んでその合計を求める問題。

考察

各お菓子の最終的な満足度は単純に \(T_i + C_i\) で求めることができます。
したがって、すべてのお菓子についてこの値を計算し、大きい順にソートすれば、上位 \(K\) 個を選ぶだけで最適解が得られます。

素朴なアプローチとして、毎回最大の満足度を持つお菓子を探す方法（例えば毎回線形探索）を取ると、時間計算量が \(O(N^2)\) となり、\(N\) が最大 \(2 \times 10^5\) なのでTLEしてしまいます。
しかし、全体を一度にソートすることで、効率的に上位 \(K\) 個を取り出すことが可能になります。

アルゴリズム

1. 各お菓子について、\(T_i + C_i\) を計算し、リストに保存する。
2. リストを降順にソートする。
3. 上位 \(K\) 個の要素の合計を求めて出力する。

例

入力例：

4 2
3 2
1 4
5 -1
2 3

計算される満足度： - お菓子1: \(3 + 2 = 5\) - お菓子2: \(1 + 4 = 5\) - お菓子3: \(5 + (-1) = 4\) - お菓子4: \(2 + 3 = 5\)

ソート後のリスト（降順）：\([5, 5, 5, 4]\)

上位2つを選ぶので、合計は \(5 + 5 = 10\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（満足度を保存するリスト）

実装のポイント

• 満足度の計算は入力を受け取るたびに行い、リストに追加するのが効率的。

• sort(reverse=True) を使うことで簡単に降順ソートができる。

• スライス [:K] を使って上位 \(K\) 個を取り出し、sum() で合計を計算。

  ソースコード

N, K = map(int, input().split())
satisfactions = []

for _ in range(N):
    T, C = map(int, input().split())
    satisfactions.append(T + C)

satisfactions.sort(reverse=True)
print(sum(satisfactions[:K]))

この解説は qwen3-coder-480b によって生成されました。