Overview

This is a problem where you can adopt at most one project from each of \(K\) categories, and you want to maximize the total expected attendance. It can be solved with a greedy approach: simply select the project with the highest expected attendance from each category.

Analysis

Key Insight

At most one project can be adopted from each category. This means the decision of “which project to adopt (or whether to adopt none)” can be made independently for each category.

When a category contains multiple projects, to maximize the total, it is clearly optimal to select the project with the maximum expected attendance \(D_i\) within that category. Since expected attendance values satisfy \(D_i \geq 1\) (positive values), it is always beneficial to adopt one project from every category that has at least one project.

Concrete Example

For instance, suppose \(K = 3\) with the following projects:

Project	Category \(B_i\)	Expected Attendance \(D_i\)
1	1	100
2	1	200
3	2	150
4	3	300

• Category 1: Project 1 (100) and Project 2 (200) → Select 200
• Category 2: Project 3 (150) → Select 150
• Category 3: Project 4 (300) → Select 300

Total: \(200 + 150 + 300 = 650\)

Comparison with a Naive Approach

Trying all combinations of adopting/not adopting each project would result in \(2^N\) possibilities, which is far too slow when \(N\) can be up to \(2 \times 10^5\). However, from the analysis above, we know that “just taking the maximum from each category” suffices, so a single pass through the \(N\) projects is enough.

Algorithm

1. Prepare a dictionary (associative array) best that maintains, for each category, the maximum \(D_i\) among projects belonging to that category.
2. Iterate through the \(N\) projects in order. For category \(B_i\), compare best[B_i] with \(D_i\) and update if the new value is larger.
3. The sum of all values in best is the answer.

This is a classic greedy algorithm. Since the choices across categories are independent of each other, making the locally optimal choice for each category directly yields the globally optimal solution.

Complexity

• Time complexity: \(O(N)\) — A single pass through all projects, with \(O(1)\) (amortized) dictionary lookup/update per project.
• Space complexity: \(O(K)\) — The size of the dictionary holding the maximum value per category (at most \(K\) entries).

Implementation Notes

• By using defaultdict(int), the initial value for categories not yet encountered is set to \(0\). Since \(D_i \geq 1\), comparing with an initial value of \(0\) ensures the first project in any category always becomes a candidate for adoption.

• Using sys.stdin.buffer.read() to read all input at once and split() to tokenize it allows fast input processing even when \(N\) is large. This is a standard technique for competitive programming in Python.

• Since expected attendance can be up to \(10^9\) and the number of categories can be up to \(2 \times 10^5\), the total can reach approximately \(2 \times 10^{14}\). Python has no integer overflow, so no special handling is needed.

  Source Code

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    best = defaultdict(int)
    for i in range(N):
        b = int(input_data[idx]); idx += 1
        d = int(input_data[idx]); idx += 1
        if d > best[b]:
            best[b] = d
    
    print(sum(best.values()))

main()

---

This editorial was generated by claude4.6opus-thinking.