Overview

Takahashi starts with skill level \(S\) and wants to raise his skill to at least the target level \(T\) by solving problems of various difficulties. He can only solve problems whose difficulty is at most his current skill level, and each problem can be solved only once. Determine whether he can achieve the target.

Analysis

In this problem, the greedy approach is key.

Key Observations

• Takahashi can only solve problems with difficulty at most his current skill level.
• Solving a problem increases his skill, allowing him to solve even more problems.
• To reach the target \(T\) as quickly as possible, it is optimal to always choose the hardest problem among those currently solvable.

Issues with a Naive Approach

For example, if we linearly search for “the hardest solvable problem” each time, the time complexity becomes \(O(N^2)\), which is too slow given the constraint that \(N\) can be up to \(2 \times 10^5\).

Solution

We use the following optimizations: 1. Sort the problem difficulties in advance so that we can add them in order as the skill level increases. 2. Use a priority queue (heap) to efficiently extract “the hardest problem among those currently solvable”. - To extract the maximum value, since Python only has a min-heap, we store negative values to manage this.

This allows us to make greedy choices efficiently.

Algorithm

1. Sort the difficulty list \(D\) in ascending order.
2. Initialize the current skill level as \(current\_skill = S\).
3. Add solvable problems to the heap while performing the following:
   • Repeat while \(current\_skill < T\).
   • Iterate through \(D\) in order, adding problems with difficulty at most \(current\_skill\) to the heap (as negative values).
   • If the heap is empty, there are no solvable problems, so output No.
   • Otherwise, extract the hardest problem (maximum difficulty) from the heap and solve it.
   • Update the skill: \(current\_skill += difficulty\)
4. Once the loop exits, the target has been achieved, so output Yes.

Concrete Example

Input:

N=3, S=2, T=10
D = [3, 5, 7]

• Skill 2 → Can solve the problem with difficulty 3.
• After solving, skill becomes 5 → Can now solve the problem with difficulty 5.
• After solving, skill becomes 10 → Target achieved!

→ Yes

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\)
  • At most \(N\) heap operations, each taking \(O(\log N)\)
• Space complexity: \(O(N)\)
  • The heap stores at most \(N\) elements

Implementation Notes

• Python’s heapq is a min-heap, so to extract the maximum value, store elements as negative values.

• By sorting the problem difficulties in advance, we can add them to the heap in order.

• Be careful about the case where the heap is empty but we still need a problem (no solvable problems remain but the target hasn’t been reached) — output No in this case.

  Source Code

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    S = int(data[1])
    T = int(data[2])
    D = list(map(int, data[3:]))

    # 最小ヒープとして使用するため、負の値で管理
    heap = []
    current_skill = S
    index = 0

    # 問題の難易度をソートしておく
    D.sort()

    while current_skill < T:
        # 解ける問題をヒープに追加（負の値で）
        while index < N and D[index] <= current_skill:
            heapq.heappush(heap, -D[index])
            index += 1
        
        # 解ける問題がない場合、終了
        if not heap:
            print("No")
            return
        
        # 最も難しい問題（最も大きい難易度）を選ぶ
        max_difficulty = -heapq.heappop(heap)
        current_skill += max_difficulty
    
    print("Yes")

if __name__ == "__main__":
    main()

---

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