概要

各クエストが「効率条件」\(R_i \ge K \times D_i\) を満たすかを判定し、満たすものの経験値 \(R_i\) を合計して \(T\) 以上になるかを調べる問題です。

考察

重要なのは、この問題では「どのクエストを選ぶか」を最適化する必要がない点です。高橋君は 効率の良いクエストだけをすべてクリアする と決まっているので、やることは次の2つだけです。

1. 各クエストについて条件 \(R_i \ge K \times D_i\) を満たすかチェックする
   
2. 満たすクエストの \(R_i\) を合計し、その合計が \(T\) 以上か判定する

素朴に考えても全探索（\(N\) 個を順に見る）で十分ですが、制約が \(N \le 2 \times 10^5\) と大きいため、不要な処理（例えばソート、DP、組合せ探索など）をすると遅くなったり実装が重くなったりします。
この問題は 1回の走査で答えが出る ので、\(N\) 回のループだけで解決できます。

また、合計経験値が \(T\) 以上になった時点でそれ以降を読む必要はありません。途中で Yes を出して終了すれば、実行時間をさらに抑えられます（早期終了）。

具体例：

• \(K=3\)、あるクエストが \((D,R)=(4,12)\) なら \(12 \ge 3 \times 4\) なのでクリア対象
• \((D,R)=(5,14)\) なら \(14 \not\ge 15\) なので対象外
  対象の \(R\) だけを足し合わせて \(T\) に届くかを見ます。

アルゴリズム

1. 入力で \(N, K, T\) を受け取る
2. 合計 total = 0 を用意する
3. \(i=1..N\) について以下を繰り返す
   
   • \(D_i, R_i\) を読む
   • もし \(R_i \ge K \times D_i\) なら total += R_i
   • もし total >= T になったら Yes を出力して終了（早期終了）
4. ループ終了後、total >= T なら Yes、そうでなければ No を出力する

計算量

• 時間計算量: \(O(N)\)（各クエストを1回ずつチェックするだけ）
• 空間計算量: \(O(1)\)（合計値など定数個の変数のみ）

実装のポイント

• \(T \le 10^{18}\) と大きいので、合計も大きくなり得ますが、Python の整数は桁あふれしないため安全です（他言語なら 64bit 整数を使う）。

• 入力が最大 \(2 \times 10^5\) 行あるため、sys.stdin.buffer.read() で高速に読み込むと安定します。

• total >= T になった瞬間に Yes を返すことで、平均的なケースで高速化できます。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    K = int(next(it))
    T = int(next(it))

    total = 0
    for _ in range(N):
        D = int(next(it))
        R = int(next(it))
        if R >= K * D:
            total += R
            if total >= T:
                print("Yes")
                return
    print("Yes" if total >= T else "No")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。