Overview

This is a problem where you can select at most one project from each category and want to maximize the total expected attendance. The conclusion is that the optimal solution is simply “select the largest \(D_i\) from each category and sum them up.”

Analysis

The key conditions are: “at most one project can be selected from each category” and “categories must not overlap.”
Under these conditions, categories do not affect each other. This is because the choice of what to select from category \(c\) depends only on “the projects within category \(c\)” and does not conflict with selections from other categories (projects from different categories can be selected simultaneously).

Therefore, for each category, the following holds:

• If selecting one project from those belonging to category \(c\), it is always optimal to choose the project with the maximum expected attendance \(D\)
• If there are no projects in category \(c\), we can simply treat it as \(0\) (select nothing)

Example:
With \(K=3\) and projects:
- Category 1: \(D=10, 30\)
- Category 2: \(D=5\)
- Category 3: (none)
The optimal solution is \(30 + 5 + 0 = 35\).

A naive approach of exhaustively searching all “combinations of selected projects” would require up to \(2^N\) possibilities, which is far too slow for \(N \le 2\times 10^5\).
However, based on the observation above, the overall optimum decomposes into “the sum of maximum values per category,” which can be solved in a single pass.

Algorithm

1. Prepare an array best of length \(K\), managing best[c] as “the maximum \(D\) seen in category \(c\)” (initialized to \(0\)).
2. Read each project \((B_i, D_i)\) and update with best[B_i] = max(best[B_i], D_i).
3. Finally, output \(\sum_{c=1}^{K} best[c]\).
   Categories with no projects remain at best[c]=0, so they are naturally ignored.

Complexity

• Time complexity: \(O(N + K)\) (\(N\) updates, plus summing \(K\) elements at the end)
• Space complexity: \(O(K)\) (storing the maximum value per category)

Implementation Notes

• \(D_i\) can be up to \(10^9\) and \(K\) can be large, so the total can reach approximately \(K \times 10^9\), but Python’s int does not overflow.

• Using sys.stdin.buffer.readline for fast I/O is recommended for safety.

• Making best of size \(K+1\) and using 1-indexed access (categories from \(1\) to \(K\)) simplifies the implementation.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    best = [0] * (K + 1)
    for _ in range(N):
        b, d = map(int, input().split())
        if d > best[b]:
            best[b] = d
    print(sum(best))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.