提出 #76486384

---

ソースコード 拡げる

import sys

# 入力の高速化
input = sys.stdin.read
data = input().split()

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

J = []
idx = 3
for _ in range(N):
    c = int(data[idx])
    v = int(data[idx + 1])
    J.append((c, v))
    idx += 2

# 価値が低い順（デフォルト）にソート。
# こうすると、J[-1] が一番価値が高くなります。
J.sort(key=lambda x: x[1])

vl = 0
used_colors = [False] * (N + 1)
used_gems = [False] * N  # どの宝石を確保したかを記録するフラグ（popの代わり）
usedCounter = 0

# 1. M種類集めるフェーズ
# リストの末尾（価値が高い方）から見ていく
ptr = N - 1
while ptr >= 0 and usedCounter < M:
    color, val = J[ptr]
    if not used_colors[color]:
        used_colors[color] = True
        used_gems[ptr] = True  # この宝石を確保したよ
        usedCounter += 1
        vl += val
    ptr -= 1

# 2. 残りの枠を埋めるフェーズ
# もう一度上（末尾）から見て、まだ確保していない宝石を上から順に取る
remains_needed = K - usedCounter
ptr = N - 1
while ptr >= 0 and remains_needed > 0:
    if not used_gems[ptr]:  # まだ確保されていない、かつ残っている中で最高価値
        vl += J[ptr][1]
        remains_needed -= 1
    ptr -= 1

print(vl)

提出情報

ジャッジ結果