English · Original
Chinese · Translation
Formal · Original
You are given an array $d_1, d_2, \dots, d_n$ consisting of $n$ integer numbers.
Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array.
Let the sum of elements of the first part be $sum_1$, the sum of elements of the second part be $sum_2$ and the sum of elements of the third part be $sum_3$. Among all possible ways to split the array you have to choose a way such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.
More formally, if the first part of the array contains $a$ elements, the second part of the array contains $b$ elements and the third part contains $c$ elements, then:
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.
The sum of an empty array is $0$.
Your task is to find a way to split the array such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.
## Input
The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in the array $d$.
The second line of the input contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$) — the elements of the array $d$.
## Output
Print a single integer — the maximum possible value of $sum_1$, considering that the condition $sum_1 = sum_3$ must be met.
Obviously, at least one valid way to split the array exists (use $a=c=0$ and $b=n$).
[samples]
## Note
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], [~]$.
你被给定一个包含 $n$ 个整数的数组 $d_1, d_2, dots.h, d_n$。
你的任务是将这个数组分成三个部分（其中一些部分可以为空），使得数组的每个元素恰好属于其中一个部分，且每个部分都是原数组的一个连续子段（可能为空）。
设第一部分的元素和为 $s u m_1$，第二部分的元素和为 $s u m_2$，第三部分的元素和为 $s u m_3$。在所有可能的分割方式中，你需要选择一种使得 $s u m_1 = s u m_3$ 且 $s u m_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$。
你的任务是找到一种分割方式，使得 $s u m_1 = s u m_3$ 且 $s u m_1$ 尽可能大。
输入的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 2 dot.op 10^5$) —— 数组 $d$ 中的元素个数。
第二行包含 $n$ 个整数 $d_1, d_2, dots.h, d_n$ ($1 lt.eq d_i lt.eq 10^9$) —— 数组 $d$ 的元素。
请输出一个整数 —— 在满足 $s u m_1 = s u m_3$ 的前提下，$s u m_1$ 的最大可能值。
显然，至少存在一种有效的分割方式（例如使用 $a = c = 0$ 且 $b = n$）。
在第一个例子中，只有一种分割方式能最大化 $s u m_1$：$[ 1, 3, 1 ], [ med ], [ 1, 4 ]$。
在第二个例子中，使 $s u m_1 = 4$ 的唯一方式是：$[ 1, 3 ], [ 2, 1 ], [ 4 ]$。
在第三个例子中，只有一种分割数组的方式：$[ med ], [ 4, 1, 2 ], [ med ]$。
## Input
输入的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 2 dot.op 10^5$) —— 数组 $d$ 中的元素个数。第二行包含 $n$ 个整数 $d_1, d_2, dots.h, d_n$ ($1 lt.eq d_i lt.eq 10^9$) —— 数组 $d$ 的元素。
## Output
请输出一个整数 —— 在满足 $s u m_1 = s u m_3$ 的前提下，$s u m_1$ 的最大可能值。显然，至少存在一种有效的分割方式（例如使用 $a = c = 0$ 且 $b = n$）。
[samples]
## Note
在第一个例子中，只有一种分割方式能最大化 $s u m_1$：$[ 1, 3, 1 ], [ med ], [ 1, 4 ]$。在第二个例子中，使 $s u m_1 = 4$ 的唯一方式是：$[ 1, 3 ], [ 2, 1 ], [ 4 ]$。在第三个例子中，只有一种分割数组的方式：$[ med ], [ 4, 1, 2 ], [ med ]$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the array.
Let $ D = (d_1, d_2, \dots, d_n) $ be a sequence of positive integers.
A **split** of $ D $ is defined by two indices $ a, b \in \{0, 1, \dots, n\} $ with $ 0 \le a \le b \le n $, partitioning the array into three contiguous parts:
- First part: $ D[1:a] = (d_1, \dots, d_a) $, sum $ s_1 = \sum_{i=1}^a d_i $
- Second part: $ D[a+1:b] = (d_{a+1}, \dots, d_b) $, sum $ s_2 = \sum_{i=a+1}^b d_i $
- Third part: $ D[b+1:n] = (d_{b+1}, \dots, d_n) $, sum $ s_3 = \sum_{i=b+1}^n d_i $
By convention, the sum over an empty range is 0.
**Constraints**
1. $ 1 \le n \le 2 \cdot 10^5 $
2. $ 1 \le d_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
3. $ 0 \le a \le b \le n $
**Objective**
Maximize $ s_1 $ subject to the constraint $ s_1 = s_3 $:
$$
\max_{\substack{0 \le a \le b \le n \\ s_1 = s_3}} s_1
$$
API Response (JSON)
{
"problem": {
"name": "C. Three Parts of the Array",
"description": {
"content": "You are given an array $d_1, d_2, \\dots, d_n$ consisting of $n$ integer numbers. Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1006C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an array $d_1, d_2, \\dots, d_n$ consisting of $n$ integer numbers.\n\nYour task is to split this array into three parts (some of which may be empty) in such a way that each element of the ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个包含 $n$ 个整数的数组 $d_1, d_2, dots.h, d_n$。\n\n你的任务是将这个数组分成三个部分（其中一些部分可以为空），使得数组的每个元素恰好属于其中一个部分，且每个部分都是原数组的一个连续子段（可能为空）。\n\n设第一部分的元素和为 $s u m_1$，第二部分的元素和为 $s u m_2$，第三部分的元素和为 $s u m_3$。在所有可能的分割方式中，你需要选择一...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array. \nLet $ D = (d_1, d_2, \\dots, d_n) $ be a sequence of positive integers. \n\nA **split** of $ D $ is defined by two indices $ a,...",
"is_translate": false,
"language": "Formal"
}
]
}