Задача №113511. Веселая игра
Однажды после очередного написанного соревнования по программированию Петя и Гена решили поиграть в какую-нибудь игру. Так как большинство современных игр кажутся им достаточно скучными, они любят придумывать свои собственные. В доступности нашлись только стикеры и ручки, но это их не остановило.
Они придумали следующую игру. Изначально они расклеили n стикеров в ряд на стене и написали на каждом стикере своё число. Далее они стали совершать ходы по очереди, причём Петя ходит первым.
В течение каждого хода происходит следующее. Пусть на стене сейчас висит m ≥ 2 стикеров. Игрок, которых ходит в данный момент, выбирает целое число k от 2 до m и забирает k стикеров с левого конца ряда себе. После этого он клеит новый стикер с левого конца ряда и пишет на нём число, равное сумме всех чисел на стикерах, которые он забрал себе на этом ходу.
Игра заканчивается, как только на стене остаётся один-единственный стикер. Счёт игрока определяется как сумма чисел, написанных на всех стикерах, которые он забрал себе. Каждый игрок стремится максимизировать разницу между своим количеством очков и количеством очков соперника.
Конечно же, Петя и Гена вкладывают другой смысл в понятие «играть в игру», нежели мы привыкли себе думать. Они уже разобрались, как по значению n и числам, написанным на каждом из стикеров исходно, определить разницу между Петиными и Гениными очками, если они будут играть оптимально. Справитесь ли вы с той же самой задачей?
В первой строке находится целое число n ( 2 ≤ n ≤ 200 000 ) — количество стикеров, которые исходно висят на стене.
Во второй строке находится n чисел a 1 , a 2 , ..., a n ( - 10 000 ≤ a i ≤ 10 000 ) — числа, написанные на стикерах в порядке слева направо.
Выведите одно число — разность между количеством очков у Пети и Гены в конце игры, если они играют оптимально.
В первом тесте из условия оптимальным ходом для Пети будет сразу взять себе все имеющиеся стикеры, в результате чего счёт Пети составит 14 , а счёт Гены — 0 .
Во втором тесте из условия оптимальная последовательность ходов для игроков выглядит следующим образом. На первом ходу Петя возьмёт себе первые три стикера и добавит слева от ряда стикер с числом - 8 . На втором ходу Гена возьмёт себе оставшиеся два стикера. Счёт Пети составит 1 + ( - 7) + ( - 2) = - 8 , а счёт Гены — ( - 8) + 3 = - 5 , значит разность очков Пети и Гены составит - 3 .
3 2 4 8
14
4 1 -7 -2 3
-3