Задан массив $$$d_1, d_2, \dots, d_n$$$, состоящий из $$$n$$$ целых чисел.
Ваша задача — разделить этот массив на три части (некоторые из которых могут быть пустыми) таким образом, что каждый элемент массива принадлежит ровно одной из частей, и каждая часть образует последовательный непрерывный подотрезок (возможно, пустой) изначального массива.
Пусть сумма элементов первой части равна $$$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$$$) — количество элементов массива $$$d$$$.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^9$$$) — элементы массива $$$d$$$.
Выведите одно целое число — максимально возможное значение $$$sum_1$$$, удовлетворяющее условию $$$sum_1 = sum_3$$$.
Очевидно, всегда существует хотя бы один способ разбить массив нужным образом (если $$$a=c=0$$$ и $$$b=n$$$).
5
1 3 1 1 4
5
5
1 3 2 1 4
4
3
4 1 2
0
В первом тестовом примере только одно возможное разбиение, которое максимизирует $$$sum_1$$$: $$$[1, 3, 1], [~], [1, 4]$$$.
Во втором тестовом примере существует единственный способ набрать $$$sum_1=4$$$: $$$[1, 3], [2, 1], [4]$$$.
В третьем тестовом примере есть только один способ разделить массив: $$$[~], [4, 1, 2], [~]$$$.
| Codeforces Round 498 (Div. 3) |
|---|
| Закончено |
