Два сборщика
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
1.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Два сборщика
На поле n×n в клетках лежат яблоки. Из левой верхней клетки в правую нижнюю по двум путям (вправо или вниз) проходят Бермет и Айбек. Яблоки каждой клетки забираются один раз, даже если через неё прошли оба. Какое наибольшее суммарное число яблок могут собрать вдвоём, выбрав пути оптимально?
Ввод. В первой строке n (1 ≤ n ≤ 40), далее n строк по n чисел (0 ≤ a_ij ≤ 9).
Вывод. Наибольшее суммарное число яблок.
Пример
Ввод:
3
0 3 1
2 5 0
1 4 7
Вывод:
22
Комментарии