Overview

This problem asks us to select \(K\) members from \(N\) members such that exactly \(M\) of them are experienced, while maximizing the total skill.

Analysis

Key Insight

The key point of this problem is the constraint “exactly \(M\) experienced members.”

• The composition of the \(K\) selected members must always be “experienced \(M\) members + beginners \((K-M)\) members”
• There’s no need to compare experienced members and beginners together; they can be selected independently

Why Can We Select Independently?

Consider the case where \(K = 3\), \(M = 1\). - We must select exactly 1 experienced member and 2 beginners - The experienced slot is competed for only among experienced members, and the beginner slots are competed for only among beginners - Therefore, we should select the top \(M\) skilled members from experienced members and the top \((K-M)\) skilled members from beginners

Concrete Example

N=5, K=3, M=1
Experienced: Skills 100, 50
Beginners: Skills 80, 70, 30

Select 1 experienced member → Top 1 by skill = 100 Select 2 beginners → Top 2 by skill = 80, 70

Answer: \(100 + 80 + 70 = 250\)

Cases Where Conditions Cannot Be Met

Selection is impossible in the following cases: - The number of experienced members is less than \(M\) - The number of beginners is less than \((K-M)\)

Algorithm

1. Classification: Separate all members into experienced (\(H=1\)) and beginners (\(H=0\))
2. Validation: Check if there are at least \(M\) experienced members and at least \((K-M)\) beginners. If insufficient, output \(-1\)
3. Sorting: Sort experienced members’ skills in descending order, and also sort beginners’ skills in descending order
4. Selection: Select the top \(M\) from experienced members and the top \((K-M)\) from beginners
5. Calculation: Output the sum of skills of the selected members

Complexity

• Time Complexity: \(O(N \log N)\)

  • \(O(N)\) to classify members
  • \(O(N \log N)\) for sorting (experienced and beginners together total \(N\) members)
  • \(O(K)\) for selecting top members and calculating the sum

• Space Complexity: \(O(N)\)

  • To store the experienced list and beginners list

Implementation Notes

1. Be careful with \(K - M = 0\) or \(M = 0\) cases: When 0 beginners are needed or 0 experienced members are needed, make sure empty list slicing and sum([]) work correctly.

2. How to use descending sort: Using sort(reverse=True) sorts in descending order. The top \(X\) members can be obtained by slicing the first \(X\) elements with [:X].

3. Large skill values: \(P_i\) can be up to \(10^9\), and the sum of \(K\) members can be approximately \(2 \times 10^{14}\). In Python, you don’t need to worry about integer overflow, but in C++ and similar languages, you need to use long long.

Source Code

def solve():
    N, K, M = map(int, input().split())
    
    experienced = []  # Experienced members (H=1)
    beginners = []    # Beginners (H=0)
    
    for _ in range(N):
        H, P = map(int, input().split())
        if H == 1:
            experienced.append(P)
        else:
            beginners.append(P)
    
    # Need exactly M experienced members and exactly K-M beginners
    num_experienced_needed = M
    num_beginners_needed = K - M
    
    # Check if conditions can be satisfied
    if len(experienced) < num_experienced_needed or len(beginners) < num_beginners_needed:
        print(-1)
        return
    
    # Select top M skilled from experienced members
    experienced.sort(reverse=True)
    selected_experienced = experienced[:num_experienced_needed]
    
    # Select top (K-M) skilled from beginners
    beginners.sort(reverse=True)
    selected_beginners = beginners[:num_beginners_needed]
    
    # Calculate total
    total = sum(selected_experienced) + sum(selected_beginners)
    
    print(total)

solve()

---

This editorial was generated by claude4.5opus.