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