概要

メンバーの中から、指定された人数の「経験者」と「初心者」を選び、スキルの合計を最大化する問題。

考察

この問題では、\(N\) 人のメンバーから \(K\) 人を選ぶが、そのうち ちょうど \(M\) 人が経験者（\(H_i = 1\)）でなければならないという制約がある。

素朴なアプローチでは？

単純には、全組み合わせを試す方法が考えられるが、
メンバー数が最大 \(2 \times 10^5\) なので、当然 TLE（時間超過）になる。

重要な観察

スキルの合計を最大化するには、
- 経験者の中からスキルが高い上位 \(M\) 人を選ぶべき
- 初心者の中からもスキルが高い上位 \((K - M)\) 人を選ぶべき

つまり、「経験者リスト」と「初心者リスト」を作り、それぞれをスキルの降順に並べておけば良い。

さらに工夫

リストをソートした後、先頭からの累積和を事前に計算しておくことで、任意の人数を選んだときのスキル合計を高速に求められる。

最後に、経験者をちょうど \(M\) 人選べるか確認し、選べない場合は -1 を出力すればよい。

アルゴリズム

1. 入力を読み込み、メンバーを「経験者」と「初心者」に分ける。
2. 両リストをスキルの降順にソートする。
3. 各リストについて、先頭からの累積和を前計算する。
4. 経験者が \(M\) 人以上、初心者が \((K - M)\) 人以上いるか確認する。
   • 足りなければ -1 を出力。
5. 経験者を \(M\) 人選ぶことを固定し、残りを初心者から選ぶ。
6. このときのスキル合計の最大値を求める。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配）
• 空間計算量: \(O(N)\) （リストと累積和の保存）

実装のポイント

• cumsum 関数のように、累積和の先頭に 0 を入れておくと、境界処理が楽になる。
• 最終的なループでは、経験者を ちょうど \(M\) 人選んでいるケースだけを考慮すること。

## ソースコード

```python
import sys
from heapq import nlargest

input = sys.stdin.read
data = input().split()

N = int(data[0])
K = int(data[1])
M = int(data[2])

members = []
idx = 3
for i in range(N):
    H = int(data[idx])
    P = int(data[idx+1])
    members.append((H, P))
    idx += 2

# 経験者と初心者に分ける
experts = [p for h, p in members if h == 1]
beginners = [p for h, p in members if h == 0]

# スキルの高い順にソート
experts.sort(reverse=True)
beginners.sort(reverse=True)

# 累積和を計算
def cumsum(arr):
    cum = [0]
    for x in arr:
        cum.append(cum[-1] + x)
    return cum

cum_experts = cumsum(experts)
cum_beginners = cumsum(beginners)

# 条件を満たすかチェック
num_experts = len(experts)
num_beginners = len(beginners)

if num_experts < M or num_beginners < (K - M):
    print(-1)
else:
    max_power = -1
    # 経験者をM人選ぶ
    for i in range(min(M, num_experts) + 1):
        if i > M or (M - i) > num_beginners:
            continue
        expert_sum = cum_experts[i] if i <= num_experts else 0
        beginner_sum = cum_beginners[K - i] if (K - i) <= num_beginners else 0
        total = expert_sum + beginner_sum
        if i == M:
            max_power = max(max_power, total)
    
    print(max_power)

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