|
Лесенка-2
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Также он поступает и дальше, пока не достигнет N-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошел Вова.
Требуется написать программу, которая определит оптимальный маршрут Вовы, при котором, шагая, он получит наибольшую сумму.
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число N – количество ступеней лестницы (2 ≤ N ≤ 1000). Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Числа, написанные на ступенях, не превосходят по модулю 1000.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать в первой строке наибольшее значение суммы. Во второй строке должны быть записаны через пробел номера ступеней по возрастанию, по которым должен шагать Вова. Если существует несколько различных правильных маршрутов, то можно вывести любой из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 2 1 | 4
1 2 3 |
| 2 | 3
1 -1 1 | 2
1 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
