Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1351. Поиск пути с максимальной суммой
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 15/02/1998 | Отборочные командные соревнования для школьников (1) |
| 27/02/2010 | Занятие 8 (A) |
| 19/11/2010 | Занятие 10 (E) |
| 09/12/2010 | Сборы: Общий итог (6E) |
| 13/01/2011 | Сборы 6: Домашнее задание (C) |
| 11/02/2013 | Занятие 16 (D) |
| 19/07/2016 | Лето 2016 - 11 (A) |
| 12/07/2021 | Лето 2021-7 (A) |
| 06/07/2022 | Лето 2022-5 (A) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дана квадратная матрица целых чисел размером N × N (1\ ≤\ N\ ≤\ 50).
Числа в матрице лежат в диапазоне от –99 до 99. Существует C_{2*(N-1)}^{N-1} возможных путей
от верхнего левого угла матрицы до нижнего правого угла, если разрешено двигаться по одной клетке вниз или вправо.
Найти путь с максимальной суммой чисел (если таких путей несколько, то вывести любой из них).
В первой строке входного файла задан размер матрицы N, в последующих N строках по N целых чисел,
разделенных одним или более пробелов (длина строки не превышает 200 символов).
В выходной файл в первой строке выводится найденный максимум, в следующей строке – числа, через которые проходит этот путь.
Пример ввода
3 1 2 3 4 5 6 1 2 3
Пример вывода
19 1 4 5 6 3
