Overview

A problem where you can select at most one project from each category, and you want to maximize the total expected attendance of the selected projects.

Analysis

In this problem, you can select at most one project per category. In other words, even if there are multiple projects in the same category, it is optimal to select only the one with the highest expected attendance.

For example, if category 1 has two projects with expected attendances of 3 and 5, you should select the one with 5 from category 1. The same applies to other categories — the optimal strategy is to select the project with the maximum expected attendance within each category.

Therefore, you just need to record the largest \(D_i\) for each category and compute their sum. A straightforward approach is to scan through all projects while updating the maximum value for each category. This is efficient and runs within the time limit without any special optimizations.

Algorithm

1. Prepare a dictionary (or array) to record the maximum expected attendance for each category.
2. While reading all projects, update the maximum value for the category each project belongs to.
3. Finally, take the sum of the maximum values across all categories.

In this way, you can optimally make selections from each category and maximize the overall total.

Complexity

• Time complexity: \(O(N)\)
  (since each project is processed exactly once)
• Space complexity: \(O(K)\)
  (since information is stored for each category)

Implementation Notes

• Category numbers are 1-indexed, so care is needed when using arrays, but using a dictionary avoids this concern.

• For speedup, it is recommended to use sys.stdin.read to read all standard input at once.

• When managing the maximum value for each category, it is sufficient to simply compare and update without checking each time whether a value already exists.

  Source Code

import sys
from collections import defaultdict

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

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

# カテゴリごとの最大集客数を保持する辞書
category_max = defaultdict(int)

index = 2
for _ in range(N):
    B = int(data[index])
    D = int(data[index+1])
    index += 2
    if D > category_max[B]:
        category_max[B] = D

# 各カテゴリから最大1つ選べるので、カテゴリごとの最大値の和が答え
result = sum(category_max.values())
print(result)

---

This editorial was generated by qwen3-coder-480b.