← 返回题目列表

AtCoder · joi2025ho_b

B. 勇敢的比特太郎 2 (勇敢的比特太郎 2)

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

勇敢的英雄Bitaro开始了打败怪物的冒险。

Bitaro有一个强度值,表示为 x,从初始值开始。 N 怪物,每个都标有数字 1 to N。为了打败 i- 第一个怪物 (1 \leq i \leq N),Bitaro 的实力至少为 A_i。击败 i第一个怪物使 Bitaro 的力量增加 B_i.

Bitaro想要使用以下策略击败所有怪物:

  1. 从特定的怪物开始 j (1 \leq j \leq N)并按顺序击败怪物: j, j + 1, \ldots, N.
  2. If j \geq 2,回去打败怪物 按顺序 1, 2, \ldots, j-1 。

给定怪物的信息,编写一个程序来确定最小初始强度 需要 x Bitaro才能击败所有怪物。


输入

从标准输入读取以下数据。

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

输出

输出单个整数,最小初始强度 x Bitaro才能击败所有怪物。


约束

  • 2 \leq N \leq 500\,000.
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N).
  • 0 \leq B_i \leq 10^9 (1 \leq i \leq N).
  • 给定值均为整数。

子任务

  1. (10 点) N \leq 2\,000,以及最小初始强度 x is 10 或更少。
  2. (21 点) N \leq 2\,000.
  3. (19 分) 最小初始强度 x is 10 或更少。
  4. (22 点) B_i = 1 (1 \leq i \leq N).
  5. (28 点)没有额外的限制。

示例输入 1

5
1 3 2 8 6
4 3 1 1 2

示例输出 1

1
  • 从初始强度开始 1.
  • 按以下顺序击败怪物:
    1. 击败怪物 1。力量增加 4 to 5.
    2. 击败怪物 2。力量增加 3 to 8.
    3. 击败怪物 3。力量增加 1 to 9.
    4. 击败怪物 4。力量增加 1 to 10.
    5. 击败怪物 5。力量增加 2 to 12.

此示例输入满足子任务的约束 1,2,3 和 5.


示例输入 2

5
1 6 3 3 2
1 2 1 0 1

示例输出 2

3
  • 从初始强度开始 3.
  • 按以下顺序击败怪物:
    1. 击败怪物 3。力量增加 1 to 4.
    2. 击败怪物 4。力量增加 0 to 4.
    3. 击败怪物 5。力量增加 1 to 5.
    4. 击败怪物 1。力量增加 1 to 6.
    5. 击败怪物 2。力量增加 2 to 8.

此示例输入满足子任务的约束 1,2,3 和 5.


示例输入 3

10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1

示例输出 3

9

此示例输入满足所有子任务的约束。


示例输入 4

7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580

示例输出 4

0

此示例输入满足子任务的约束 1,2,3 和 5.