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