No.1570 Blocks
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 64
作問者 : maguro / テスター : blackyuki PCTprobability
タグ : / 解いたユーザー数 64
作問者 : maguro / テスター : blackyuki PCTprobability
問題文最終更新日: 2021-04-20 21:50:53
問題文
$N$ 個のブロックがあります。ブロック $i\ (1 \leq i \leq N)$ は重さが $A_i$ で耐荷重が $B_i$ です。
この時、全てのブロックを以下の条件を満たすように $1$ 列に積み上げることは出来るでしょうか?
- 全てのブロック $i$ について、ブロック $i$ よりも上に積まれたブロックの重さの総和が $B_i$ を超えない。
入力
$N$ $A_1\ B_1$ $A_2\ B_2$ $\vdots$ $A_N\ B_N$
- 入力は全て整数である。
- $1 \leq N \leq 10^5$
- $1 \leq A_i,B_i \leq 10^9$
出力
全てのブロックを条件を満たすように $1$ 列に積み上げることが可能ならYes
を、不可能ならNo
を出力してください。最後に改行してください。
サンプル
サンプル1
入力
4 2 3 2 4 1 5 4 5
出力
Yes
例えば、上から順にブロック $1$ 、ブロック $3$ 、ブロック $2$ 、ブロック $4$ と積むと条件を満たします。
サンプル2
入力
3 6 5 4 5 2 2
出力
No
どう積んでも条件を満たすことが出来ません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。