問題一覧 > 通常問題

No.1583 Building Blocks

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : magstamagsta / テスター : shino16shino16
2 ProblemId : 6231 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-02 19:28:59

問題文

$N$ 個の積み木があります。$i$ 個目の積み木の重さは $w_i$ で、硬さは $s_i$ です。

以下の条件を満たすように、1 個以上の積み木を選んでそれらを積み上げることを考えます。最大で何個の積み木を積み上げられるかを求めてください。

条件

積み上げた全ての積み木それぞれ (積み木 P とする) において、積み木 P より上にある積み木 (積み木 P を含まない) の重さの合計が、積み木 P の硬さ以下である。

より厳密な問題文

整数 $N$ が与えられます。また、$N$ 個の整数 $w_1, w_2,…, w_N$ と、$N$ 個の整数 $s_1, s_2,…, s_N$ が与えられます。

以下の条件を満たすように、空でない整数列 $A$ を作ることを考えます。考えられる $A$ の要素数で最大のものを求めてください。

条件

  • (要素数はいくつでもよい。便宜上、ここでは要素数を $X$ としておく。)
  • $1 \leq i \leq X$ を満たす全ての $i$ において、$1 \leq A_i \leq N$
  • $1 \leq i,j \leq X$ かつ $i \neq j$ を満たす全ての ($i, j$) において、$A_i \neq A_j$
  • $1 \leq i \leq X$ を満たす全ての $i$ において、$\displaystyle \sum_{k=1}^{i - 1} w_{A_k} \leqq s_{A_i}$
(整数列 $A$ の $i$ 個目の要素を $A_i$ と表記しています。)

入力

$N$
$w_1\ \ s_1$
$w_2\ \ s_2$
$:$
$w_N\ \ s_N$

  • $1 \leq N \leq 10^3$
  • $1 \leq w_i, s_i \leq 10^9$
  • 入力はすべて整数である

出力

求めた値を出力し、最後に改行せよ。

サンプル

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

下から順に積み木 2、積み木 1 を積み上げると積み木を 2 個積み上げたことになります。 積み木を 3 個積み上げることはできないため、2 個積み上げるのが最大となります。

サンプル2
入力
8
23907824 512
347613 276
29074 981
409801 837
2939123 285
1087432 18
1238930 9832
287931 23
出力
1

2 個以上積み上げることはできません。

サンプル3
入力
20
702942310 384194029
229351257 240012589
888749549 277038040
894642151 627015876
807346218 681631935
635995728 25027850
25753102 594612993
59739707 245417032
643586787 827447411
578510634 515373169
749153251 734083014
280524008 353961256
293345690 296823276
543870074 113249829
427006969 902166637
885344786 189584191
207361148 780822106
547181796 158349222
741195942 95500093
820886476 460559617
出力
6

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