Overview

Starting from an initial skill level \(S\), this problem asks you to determine whether you can reach a target skill level \(T\) by solving problems (those with difficulty at or below your current skill level) to increase your skill.

Analysis

Key Observations

1. Condition to solve a problem: You can solve a problem when its difficulty \(D_i\) is at or below your current skill level
2. Skill growth: Solving a problem increases your skill by the amount of that problem’s difficulty
3. Each problem can be solved at most once: You cannot solve the same problem multiple times

Why a Greedy Approach is Optimal

There is a property that “if there are solvable problems, the total skill increase is the same regardless of the order in which you solve them.”

For example, with skill \(S = 5\) and problems of difficulty \(3\) and \(4\) both solvable: - Order \(3 → 4\): \(5 → 8 → 12\) - Order \(4 → 3\): \(5 → 9 → 12\)

The final skill is the same in both cases.

However, solving problems in order of increasing difficulty is important. This is because at a low skill level, you cannot solve high-difficulty problems.

Example: Skill \(S = 5\), problems with difficulty \(6, 3\) - Difficulty \(6\) cannot be solved initially (\(6 > 5\)) - Solve difficulty \(3\) first: \(5 → 8\) - Now difficulty \(6\) becomes solvable: \(8 → 14\)

Why Sorting and Processing in Order is Sufficient

By sorting difficulties in ascending order and solving solvable problems sequentially, we never “miss a problem we should have been able to solve.” If a problem of difficulty \(d\) is solvable, all problems with lower difficulty must have already been solved before it.

Algorithm

1. Sort the difficulty array \(D\) in ascending order
2. Initialize the current skill current_skill to \(S\)
3. Iterate through the sorted difficulties in order:
   • If current_skill >= T, the goal is achieved, so terminate
   • If difficulty \(d\) is at most current_skill, solve the problem and update current_skill += d
4. After the loop, output Yes if current_skill >= T, otherwise No

Example: N=3, S=5, T=15, D=[6, 3, 8]
After sorting: D=[3, 6, 8]

current_skill = 5
- d=3: 3 <= 5, so solve it → current_skill = 8
- d=6: 6 <= 8, so solve it → current_skill = 14
- d=8: 8 <= 14, so solve it → current_skill = 22

22 >= 15, so the answer is "Yes"

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\)
  • The loop takes \(O(N)\)
• Space complexity: \(O(N)\)
  • For storing the difficulty array

Implementation Notes

1. Don’t forget to sort: Processing problems in order of increasing difficulty is essential for the greedy approach to work correctly

2. Watch out for overflow: \(S, T\) can be as large as \(10^{18}\), but in Python there is no integer overflow issue so this is not a problem (in C++ and similar languages, caution is needed)

3. Early termination: Breaking out of the loop as soon as the goal is achieved avoids unnecessary computation (the solution works correctly without this optimization as well)

   Source Code

def solve():
    N, S, T = map(int, input().split())
    D = list(map(int, input().split()))
    
    # 難易度でソート
    D.sort()
    
    current_skill = S
    
    # 貪欲に解ける問題を解いていく
    for d in D:
        if current_skill >= T:
            break
        if d <= current_skill:
            current_skill += d
    
    if current_skill >= T:
        print("Yes")
    else:
        print("No")

solve()

---

This editorial was generated by claude4.5opus.