問題一覧 > 通常問題

No.3422 Sazanka's hobby

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : harel / テスター : まみめ rogi52 Guran08 syndrome hirayuu_yc 遭難者 kidodesu 👑 ArcAki Eku
ProblemId : 12868 / yukicoder contest YNUCPC Contest 2 (順位表) / 自分の提出
問題文最終更新日: 2026-01-12 09:43:06
yukicoder contest YNUCPC Contest 2の他の問題:

問題文

　Sazankaくんは $N$ 本の植物を育てている。$i$ 番目の植物の $1$ 日目の朝の高さは $a_i$ であり、毎日夜の間に $b_i$ だけ成長して高くなる。
　Sazankaくんの部屋の高さは $M$ であり、それより植物が高くなると天井を突き破り、部屋が雨漏りしてしまう。これを防ぐため、Sazankaくんは毎朝、最大 $k$ 本まで部屋から取り除くことにしている。
　Sazankaくんは出来る限り長く植物を眺めていたいので、部屋が雨漏りせずに済むようにするために必要な最小の $k$ を求めることにした。

制約

  • $1 \leq N \leq10^6$
  • $1 \leq M \leq10^9$
  • $0 \leq a_i \leq M$
  • $1\leq b_i \leq10^9$
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$  
$a_1$ $b_1$  
$a_2$ $b_2$  
⋮  
$a_N$ $b_N$

出力

部屋が雨漏りせずに済むようにするために必要な最小の $k$ を出力せよ。

サンプル

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

$1$ 日目の夜に、植物の長さはそれぞれ $4,5,5$ になります。$2$ 日目の夜には $6,8,7$ となります。
$k = 1$ とすると、$2$ 日目の夜までに最大で $2$ 本しか取り除くことができないため、残り $1$ つの植物が天井を突き破ります。
$k = 2$ とすることで、雨漏りを防ぐことが出来ます。

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

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