Overview

This is a problem where Aoki must be included in the team, and the remaining members are selected from other players in descending order of skill values.

Analysis

Understanding the Problem

In this problem, we form a team of \(K\) people from \(N\) candidate players. However, the following constraints apply: - Player \(T\) (Aoki) must be included as a member - The remaining \(K-1\) people are selected from players other than Aoki in descending order of skill values

Key Observations

1. Since Aoki unconditionally joins the team, Aoki’s skill value \(A_T\) is always included in the total
2. The remaining players are \(N-1\) people excluding Aoki
3. We simply need to select the top \(K-1\) people with the highest skill values from those \(N-1\) people

Thinking Through a Concrete Example

For example, with \(N=5\), \(K=3\), \(T=2\), and skill values \(A = [10, 5, 30, 20, 15]\): - Aoki’s (player 2) skill value is \(5\) - Skill values of players other than Aoki are \([10, 30, 20, 15]\) - Sorting in descending order gives \([30, 20, 15, 10]\) - Selecting the top \(K-1=2\) people gives players with skill values \(30\) and \(20\) - The total is \(5 + 30 + 20 = 55\)

Is a Naive Approach Sufficient?

For this problem, an approach using sorting is fast enough. For \(N \leq 2 \times 10^5\), an \(O(N \log N)\) sort runs with plenty of room to spare.

Algorithm

1. Get Aoki’s skill value \(A_{T-1}\) (0-indexed)
2. Collect the skill values of all players except Aoki into a list
3. Sort that list in descending order (highest first) of skill values
4. Extract the skill values of the first \(K-1\) people from the sorted list
5. Output the sum of Aoki’s skill value and the skill values of the extracted \(K-1\) people

Aoki's skill value + (sum of skill values of top K-1 people excluding Aoki)

Complexity

• Time Complexity: \(O(N \log N)\)
  • Collecting players other than Aoki into a list: \(O(N)\)
  • Sorting: \(O(N \log N)\)
  • Calculating the sum of top \(K-1\) people: \(O(K)\)
  • Overall, \(O(N \log N)\) is dominant
• Space Complexity: \(O(N)\)
  • \(O(N)\) for the list storing skill values of players other than Aoki

Implementation Notes

1. Index Conversion: In the problem statement, player numbers start from 1 (1-indexed), but Python lists start from 0 (0-indexed), so Aoki’s index becomes T-1.

2. Excluding Aoki: Loop through all players and add only those whose index is not T-1 to a separate list.

3. Descending Sort: Using sort(reverse=True) arranges the skill values in descending order.

4. Calculating the Sum: You could use slicing like sum(others[:K-1]), but the code explicitly adds using a loop. Either approach works correctly.

Source Code

def solve():
    N, K, T = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Aoki's skill value (T-1 because of 0-indexing)
    aoki_power = A[T - 1]
    
    # List of skill values for players other than Aoki
    others = []
    for i in range(N):
        if i != T - 1:
            others.append(A[i])
    
    # Sort in descending order of skill values
    others.sort(reverse=True)
    
    # Sum of Aoki + remaining K-1 players' skill values
    total = aoki_power
    for i in range(K - 1):
        total += others[i]
    
    print(total)

solve()

---

This editorial was generated by claude4.5opus.