printРабочее место участника

printЗадачи

1371. Игра перед чаепитием

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11221.png
Чтобы убить время перед чаепитием, Мартовский Заяц и Болванщик играют в следующую игру. Игра идет на части квадрата размером `N\ times\ N` клеток, разрезанного по диагонали. В диагональных клетках записаны некоторые числа. В левый нижний угол доски помещается фишка. Игроки по очереди двигают фишку на соседнюю клетку вверх, вправо или по диагонали вверх-вправо, пока фишка не окажется на диагонали квадрата. Игрок, достигший клетки на диагонали квадрата, получает выигрыш, равный числу, записанному в этой клетке (отрицательное число в этой клетке означает проигрыш игрока).
Напишите программу, вычисляющую максимальный выигрыш, который может получить игрок, делающий первый ход, при оптимальной игре обоих игроков.
Первая строка содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 1000`) – размер доски, вторая строка – `N` целых чисел в диапазоне от `-10^6` до `10^6` – числа на диагонали.
Вывести одно целое число – максимальный выигрыш первого игрока.

Пример ввода

7
7 1 4 9 -3 9 2

Пример вывода

3
loading