Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1371. Игра перед чаепитием
Динамическое программирование и запоминающие функцииОбход дерева игры, α-β процедура
Олимпиадные задачи на русском языке
| 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) |
Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Чтобы убить время перед чаепитием, Мартовский Заяц и Болванщик играют в следующую игру.
Игра идет на части квадрата размером `N\ times\ N` клеток, разрезанного по диагонали.
В диагональных клетках записаны некоторые числа. В левый нижний угол доски помещается фишка.
Игроки по очереди двигают фишку на соседнюю клетку вверх, вправо или по диагонали вверх-вправо, пока фишка не
окажется на диагонали квадрата. Игрок, достигший клетки на диагонали квадрата, получает выигрыш, равный числу,
записанному в этой клетке (отрицательное число в этой клетке означает проигрыш игрока).
Напишите программу, вычисляющую максимальный выигрыш, который может получить игрок, делающий первый ход,
при оптимальной игре обоих игроков.
Первая строка содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 1000`) – размер доски, вторая строка – `N` целых чисел в
диапазоне от `-10^6` до `10^6` – числа на диагонали.
Вывести одно целое число – максимальный выигрыш первого игрока.
Пример ввода
7 7 1 4 9 -3 9 2
Пример вывода
3
