← 返回题目列表

AtCoder · kupc2020_e

E. 序列分区

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

配点 : 300 点

問題文

-10^9 以上 10^9 由以下整数构成,长度为 N 序列 使用 A=(a_0,...,a_{N-1}),B=(b_0,...,b_{N-1}),C=(c_0,...,c_{N-1}) 。 满足

现在,数列 A 分割为几个连续的子序列。分割是由满足以下 3 条件的整数序列 D=(d_0,...,d_r) 表示的。也就是说,每个

  • d_0=0
  • d_r=N
  • d_i < d_{i+1} (0 \leq i < r)

表示一个连续区间,整个数列是这 i , [d_i,d_{i+1}) 个区间的并集。对于 r 返回 sukua 的函数

分割 D 针对…返回sukoa的函数 f 定义如下。 当巧妙地选择

\displaystyle f(D)=\min_{0 \leq i < r}\left\{b_{d_i}+c_{d_{i+1}-1}+\sum_{d_i \leq j < d_{i+1}} a_j\right\}

分割时, 请找到f 的最大值。 当

制約

  • 所有输入均为整数。
  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq a_i,b_i,c_i \leq 10^9(0 \leq i < N)

入力

输入是按以下格式从标准输入给出的。

N
a_0 a_1 \cdots a_{N-1}
b_0 b_1 \cdots b_{N-1}
c_0 c_1 \cdots c_{N-1}

出力

答案 行 1 行。


入力例 1

2
1 -1
-1 4
1 -2

出力例 1

1

D=(0,2) 时,sukoa 是 b_0+c_1+a_0+a_1=-3 。

D=(0,1,2) 时,sukoa 是 \min(b_0+c_0+a_0,b_1+c_1+a_1)=\min(1,1)=1 。


入力例 2

1
1000000000
1000000000
1000000000

出力例 2

3000000000

小心溢出。


入力例 3

11
-323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840
-696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217
-465411342 -660775657 515997870 -34787742 628368976 84800619 -728713779 573207953 115652694 -686953578 -215986240

出力例 3

91174984