Overview

Starting from an initial skill level \(S\), this problem asks you to determine whether you can reach the target \(T\) or higher by solving problems with difficulty \(D_i\) to raise your skill.

Analysis

The core of this problem lies in the question: “In what order should we solve the problems optimally?”

For Takahashi to solve a problem, his current skill level must be at least the difficulty of that problem. Since solving a problem increases his skill level, the more problems he solves, the more “options for the next solvable problem” become available.

There is no benefit to trying to solve harder problems first. This is because solving hard problems requires high skill, but if you solve easier problems first to build up your skill, the chances of being able to solve those hard problems later increase.

Therefore, the optimal strategy is the greedy approach: “Among the currently solvable problems, always solve the one with the lowest difficulty first.” Sort problems in ascending order of difficulty and check them one by one. If you encounter a problem that your current skill cannot solve, all subsequent problems (which have even higher difficulty) are also impossible to solve, so you can terminate the search there.

Algorithm

The determination is performed using the following steps:

1. If the initial skill level \(S\) is already at or above the target \(T\), immediately output Yes and terminate.
2. Sort the given difficulty list \(D\) in ascending order (from smallest to largest).
3. Take each sorted difficulty one at a time and repeat the following process:
   • If the current skill level \(\ge\) the extracted difficulty \(D_i\), solve the problem and add \(D_i\) to the skill level.
   • If the skill level after addition reaches \(T\) or above, output Yes and terminate.
   • If difficulty \(D_i\) is greater than the current skill level, neither this problem nor any subsequent problems can be solved, so break out of the loop.
4. If the loop completes without reaching \(T\), output No.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting \(N\) elements takes \(O(N \log N)\). The subsequent list traversal is \(O(N)\), so the overall complexity is dominated by the sorting step.
  • With the constraint \(N \leq 2 \times 10^5\), this complexity is well within the time limit.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array (list) holding the difficulties of the \(N\) problems.

Implementation Notes

• Early termination: By immediately outputting Yes when \(S \ge T\) in the initial state or when \(T\) is exceeded midway, unnecessary computation can be avoided.

• Using sort: Using the sorted() function or the .sort() method to reorder difficulties is the most important step in solving this problem.

• Handling large numbers: Since \(S\) and \(T\) can be very large values up to \(10^{18}\), overflow must be considered depending on the language. However, in Python, arbitrarily large integers are handled natively, so calculations can be performed directly without any issues.

  Source Code

import sys

def main():
    # 入力を一度に読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 問題数, S: 初期スキルレベル, T: 目標スキルレベル
    n = int(input_data[0])
    s = int(input_data[1])
    t = int(input_data[2])
    
    # すでに目標スキルレベルに達している場合
    if s >= t:
        print("Yes")
        return
    
    # 各問題の難易度を整数に変換し、昇順にソートします（貪欲法）
    # 難易度の低い問題から解くことで、より多くの問題を解ける可能性が高まります
    d_list = sorted(map(int, input_data[3:]))
    
    current_skill = s
    for d in d_list:
        # 現在のスキルレベルで解ける問題か判定
        if current_skill >= d:
            # スキルレベルを問題の難易度分だけ上昇させる
            current_skill += d
            # 目標スキルレベルに達したか判定
            if current_skill >= t:
                print("Yes")
                return
        else:
            # 難易度順に並んでいるため、現在のスキルで解けない問題が現れたら
            # それ以降の全ての問題も解くことができません
            break
    
    # 全ての問題を検討しても目標に達しなかった場合
    print("No")

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-preview.