難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) 未投票 (0票)

投票の分布

まだ投票はありません。

  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.50票
  6. Lv.60票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Melting Kotatsu Cats

作成者 jammy

テスター tau0529

難易度(作成者設定) Lv.3

難易度(投票) 未投票 (0票)

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

1からNNまでの番号のついたNN匹の猫と1台のこたつがあります。ii番目の猫は最初は大きさViV_iですが、 こたつに入った猫iiは温まって溶けるため大きさが DiD_i だけ大きくなります。(1≤i≤N1 \le i \le N)
つまり体の大きさがVi+DiV_i+D_iになります。 なるべく多くのねこちゃんたちをこたつにいれてあげたいですが、こたつは狭いので以下の条件を設けることにしました。

こたつにxx匹の猫が入り、その猫たちが十分に溶けた後
xx匹の猫の大きさの合計がN−xN-x匹の猫の大きさの合計以下になる。

上の条件を満たすような最大のxxを求めてください。

制約

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤Vi≤1091 \le V_i \le 10^9
  • 0≤Di≤1090 \le D_i \le 10^9
  • 入力はすべて整数

入力

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

NN V1V_1 V2V_2 ... VNV_N D1D_1 D2D_2 ... DND_N

出力

答えを出力せよ。

サンプル 1

入力

5
9 7 5 6 10
2 3 9 6 9

22 番目と 44 番目のねこちゃんをこたつにいれて十分に溶かすと、こたつに入ったねこちゃんたちの大きさは {10,12}\{10, 12\} になります。

そのときこたつにいるねこちゃんの大きさの総和と、そうでないねこちゃんの大きさの総和は以下のようになります。

こたつにいる: 10+12=2210 + 12 = 22
こたつにいない: 9+5+10=249 + 5 + 10 = 24

22≤2422 \leq 24 より、こたつに入るねこちゃんの数 x=2x = 2 は条件を満たします。

また、条件を満たしつつ x=2x = 2 より多くのねこちゃんをこたつに入れることはできないので、求める最大の xx は 22 となります。

出力

2

サンプル 2

入力

4
9 7 9 8
0 4 0 2

出力

1