0040. Спуск с горы

Имя входного файла:	slalom.in
Имя выходного файла:	slalom.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

В одном из горнолыжных курортов Италии, проводится соревнования по горнолыжному спуску. Каждому спортсмену предстоит скатиться с горы на лыжах.

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

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

Требуется найти максимальное количество очков, которое может набрать спортсмен.

Формат входного файла

Во входном файле содержится целое число n – число этапов (1 ≤ n ≤ 100), далее n строк, каждая из которых характеризует свой уровень. В строке с номером i содержится ровно i чисел: a1, a2, ..., ai (-100 ≤ ak ≤ 100, 1 ≤ k ≤ i) – количество очков в каждой из позиций.

Формат выходного файла

В результирующем файле должно находится искомое целое число.

Пример:

slalom.in	slalom.out
4 1 4 3 5 6 7 8 9 0 9	20

Источник: Petrozavodsk training camp, Summer 2002. DNK contest
Автор: Denis Davydov (DNK team)

Обсудить       Отправить решение