Codeforces Round 655 (Div. 2) |
---|
Закончено |
Дэнни, местный математик-маньяк, очарован кругами, самым последним творением Омкара. Помогите ему решить эту задачу о круге!
Вам даны $$$n$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_n$$$, расположенных по кругу, где $$$n$$$ гарантированно будет нечетным (т.е. $$$n-1$$$ делится на $$$2$$$). Формально для всех $$$i$$$ таких, что $$$2 \leq i \leq n$$$, элементы $$$a_{i - 1}$$$ и $$$a_i$$$ считаются соседними, а $$$a_n$$$ и $$$a_1$$$ также рассматриваются как соседние. За одну операцию вы выбираете число в круге, заменяете его суммой двух соседних элементов, а затем удаляете два соседних элемента из круга. Это повторяется до тех пор, пока в круге не останется только одно число, которое мы называем круговым значением.
Помогите Дэнни найти максимально возможное круговое значение после некоторой последовательности операций.
Первая строка содержит одно нечетное целое число $$$n$$$ ($$$1 \leq n < 2 \cdot 10^5$$$, $$$n$$$ нечетно) — начальный размер круга.
Вторая строка содержит $$$n$$$ целых чисел $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$0 \leq a_{i} \leq 10^9$$$) — начальные числа в круге.
Выведите максимально возможное круговое значение после применения некоторой последовательности операций к данному кругу.
3 7 10 2
17
1 4
4
Для первого примера круговое значение $$$17$$$ получается так:
Выберите число с индексом $$$3$$$. Сумма соседних элементов равна $$$17$$$. Удалите $$$7$$$ и $$$10$$$ из круга и замените $$$2$$$ на $$$17$$$.
Обратите внимание, что ответ может выйти за пределы $$$32$$$-разрядного целого числа.
Название |
---|