E - Sequence Partitioning Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 個の区間の和集合になっています。

分割 D に対してスコアを返す関数 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) のとき、スコアは b_0+c_1+a_0+a_1=-3 となります。

D=(0,1,2) のとき、スコアは \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