CF1006C Three Parts of the Array

**问题描述** 给定一个长度为n的整数序列$\{d_1,d_2,\dots,d_n\}$。 你的任务是将序列分成3部分，每部分可以是空的，并保证每一个数都属于这三个部分的某一个，每一部分都必须是一些连续的整数。 设三部分的和分别为$sum_1$,$sum_2$,$sum_3$。 那么你需要在所有划分方案中找到一个方案使得$sum_1=sum_3$且$sum_1$尽可能的大。 确切的说，如果第一部分包含$a$个整数，第二部分包含$b$个整数而第三部分包含$c$个，那么应该有 $$sum_1 = \sum\limits_{1 \le i \le a}d_i,$$ $$sum_2 = \sum\limits_{a + 1 \le i \le a + b}d_i,$$ $$sum_3 = \sum\limits_{a + b + 1 \le i \le a + b + c}d_i.$$ 并且对于空的那部分，它的和为0。 你需要在所有划分方案中找到一个方案使得$sum_1=sum_3$且$sum_1$尽可能的大。

第一行一个整数$n(1 \le n \le 2 \cdot 10^5)$ 第二行包含n个整数$d_1, d_2, \dots, d_n(1 \le d_i \le 10^9)$

一行一个整数，表示$sum_1$的最大值 显然，至少有一种划分方案是合法的$(a=c=0,b=n)$

In the first example there is only one possible splitting which maximizes $ sum_1 $ : $ [1, 3, 1], [~], [1, 4] $ . In the second example the only way to have $ sum_1=4 $ is: $ [1, 3], [2, 1], [4] $ . In the third example there is only one way to split the array: $ [~], [4, 1, 2], [~] $ .