Падение по колонкам


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Падение по колонкам

Шарик падает по полю n×m сверху вниз. Из клетки (i, j) он может перейти в клетку (i+1, j−1), (i+1, j) или (i+1, j+1), если она есть на поле. За каждую посещённую клетку шарик платит её значение. Начать можно с любой клетки верхней строки, закончить в любой клетке нижней. Какая наименьшая плата возможна?

Ввод. В первой строке n и m (1 ≤ n, m ≤ 500), далее n строк по m чисел (−100 ≤ a_ij ≤ 100).

Вывод. Наименьшая плата.

Пример

Ввод:

3 3
2 1 3
6 5 4
7 8 9

Вывод:

13

Комментарии

Еще нет ни одного комментария.