問題一覧 > 通常問題

No.2056 非力なレッド

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

問題文

勇者 taiga 君は $N$ 体のモンスターを倒そうとしています。taiga 君の戦闘力は $X$ であり、 mp は $M$ です。またモンスター $i$ の戦闘力は $A_i$ です。 taiga 君はモンスターと戦闘する前に次の魔法を $0$ 回以上使うことができます。

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

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

入力

$N$ $X$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

  • $1 \le N \le 2×10^5$
  • $1 \le X \le 10^9$
  • $0 \le M \le 10^9$
  • $1 \le A_i \le 10^9$
  • 入力は全て整数
  • 出力

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

    サンプル

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

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

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

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

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

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