← 返回题目列表

AtCoder · awc0061_b

B. 山路远足

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

分数: 300 分

问题陈述

高桥打算尝试山路徒步路线。

这个徒步路线有 N 检查点,从检查点开始编号 1 to N。路线是单线,高桥从检查站出发 1 并按检查点顺序进行 1, 2, 3, \ldots, N。高桥可以在他喜欢的任何检查站结束徒步旅行。也就是说,他可能会停在一个中间检查点而不再继续前进,或者他可能会一直走到检查点 N.

每个检查点 i (1 \leq i \leq N) 有一个“风景分数” S_i 分配给它。当高桥到达检查站时 i,他获得风景分数 S_i。另一方面,从检查站出发 i 前往检查点 i+1 消耗体力消耗 C_i (1 \leq i \leq N-1).

高桥在某个检查站结束徒步 k (1 \leq k \leq N)。此时,高桥的“徒步满意度”由以下公式计算:

\left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right)

也就是说,是通过关卡获得的风景总分 1 通过 k,减去从检查站出发所需的总体力消耗 1 前往检查点 k。当 k = 1,没有发生任何移动,因此总体力消耗为 0,满意度为 S_1.

求高桥最优选择结束徒步的检查点时“徒步满意度”的最大值。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N-1)
  • 所有输入均为整数。

输入

输入由以下格式的标准输入给出。

N
S_1 S_2 \ldots S_N
C_1 C_2 \ldots C_{N-1}
  • 第一行包含一个整数 N 代表检查点的数量。
  • 第二行包含 N 整数 S_1, S_2, \ldots, S_N 以空格分隔,代表每个关卡的风景分数。
  • 第三行包含 N-1 整数 C_1, C_2, \ldots, C_{N-1} 以空格分隔,代表相邻检查点之间的体力消耗。在这里, C_i 是从检查点移动的耐力消耗 i 前往检查点 i+1。然而,当 N = 1,第三行是空行。

输出

在单行中输出“徒步满意度”的最大值。


示例输入 1

5
5 3 8 2 6
4 10 1 3

示例输出 1

6

示例输入 2

4
10 1 1 1
100 100 100

示例输出 2

10

示例输入 3

12
7 15 3 20 6 8 25 4 10 12 5 18
5 12 4 30 2 7 20 1 15 3 9

示例输出 3

25

示例输入 4

20
13 8 21 5 34 2 18 27 6 11 40 3 16 9 25 7 30 4 14 22
6 20 4 10 30 1 15 35 2 8 12 25 5 18 3 28 7 9 11

示例输出 4

66

示例输入 5

1
1000000000

示例输出 5

1000000000