問題一覧 > 通常問題

No.2056 非力なレッド

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 160
作問者 : taiga0629kyopro / テスター : 👑 ygussany
2 ProblemId : 8419 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-23 02:12:03

問題文

勇者 taiga 君は NN 体のモンスターを倒そうとしています。taiga 君の戦闘力は XX であり、 mp は MM です。またモンスター ii の戦闘力は AiA_i です。 taiga 君はモンスターと戦闘する前に次の魔法を 00 回以上使うことができます。

  • 1kmin(N,M)1 \le k \le \mathrm{min}(N,M) を満たす整数 kk を一つ選び、1ik1 \le i \le k を満たす全ての整数 ii に対して AiA_iAi2\left\lfloor \frac{A_i}{2} \right\rfloorに置き換える。 その後 MMMkM-k に置き換える。

taiga 君がモンスターと戦闘すると、X>max1iNAiX > \displaystyle \max_{1 \le i\le N}A_i のときに限り NN 体のモンスターを全て倒すことができ、そうでないときは taiga 君はモンスターを 11 体も倒すことができずに負けてしまいます。 戦闘前に適切に魔法を使うことで taiga 君は NN 体のモンスターを倒すことができますか?

入力

NN XX MM
A1A_1 A2A_2 \dots ANA_N

  • 1N2×1051 \le N \le 2×10^5
  • 1X1091 \le X \le 10^9
  • 0M1090 \le M \le 10^9
  • 1Ai1091 \le A_i \le 10^9
  • 入力は全て整数
  • 出力

    taiga 君が NN 体のモンスターを倒すことができるなら Yes と、そうでないなら No と出力してください。

    サンプル

    サンプル1
    入力
    3 3 3
    6 4 2
    出力
    Yes

    まず k=2k=2 を選ぶと A=(3,2,2)A=(3,2,2) となります。次に k=1k=1 を選ぶと A=(1,2,2)A=(1,2,2) となり、max(A)<X\max(A) < X とすることができます。

    サンプル2
    入力
    3 3 2
    1 1 4
    出力
    No

    max(A)<X\max(A) < X とするには k=3k=3 を選び A=(0,0,2)A=(0,0,2) とする必要がありますが、M<3M < 3 なのでそれは不可能です。

    サンプル3
    入力
    4 3 3
    3 1 4 1
    出力
    Yes

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。