07/04/2025 02:47:34

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

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

Чтобы убить время перед чаепитием, Мартовский Заяц и Болванщик играют в следующую игру. Игра идет на части квадрата размером

$N\ times\ N$ клеток, разрезанного по диагонали. В диагональных клетках записаны некоторые числа. В левый нижний угол доски помещается фишка. Игроки по очереди двигают фишку на соседнюю клетку вверх, вправо или по диагонали вверх-вправо, пока фишка не окажется на диагонали квадрата. Игрок, достигший клетки на диагонали квадрата, получает выигрыш, равный числу, записанному в этой клетке (отрицательное число в этой клетке означает проигрыш игрока).

Напишите программу, вычисляющую максимальный выигрыш, который может получить игрок, делающий первый ход, при оптимальной игре обоих игроков.

Первая строка содержит одно целое число

$N$ (

$2\ ≤\ N\ ≤\ 1000$ ) – размер доски, вторая строка –

$N$ целых чисел в диапазоне от

$-10^6$ до

$10^6$ – числа на диагонали.

Вывести одно целое число – максимальный выигрыш первого игрока.

Пример ввода

7
7 1 4 9 -3 9 2

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

20/03/2010	Южно-Уральский открытый командный чемпионат по программированию (C)
11/02/2013	Занятие 16 (E)
19/11/2013	Занятие 9 для начинающих (D)
07/07/2016	Лето 2016 - 6 (командная) (C)
13/07/2018	Лето 2018 - 9 (командные) (F)
12/07/2021	Лето 2021-7 (C)
02/03/2023	Базовый уровень: динамическое программирование 2 (проводит BOGAT) (C)
06/03/2023	Игры 1 (проводит BOGAT) (B)
05/03/2024	Динамическое программирование 2 (проводит BOGAT) (C)
07/03/2024	ДП (повторение) (проводит BOGAT) (E)
17/03/2025	ЦОП2: Игры 1 (проводит BOGAT) (D)