e-olymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

Ограбление домов

Вы – профессионал своего дела и планируете ограбить ряд домов вдоль улицы. В каждом доме спрятана определенная сумма денег. Единственное, что мешает Вам грабить – так это то, что соседние дома связаны системой безопасности: будет передан сигнал в полицию, если два соседние дома будут ограблены в один и тот же вечер.

Зная количество денег в каждом доме, определите максимальную сумму, которую Вы сможете ограбить сегодня вечером без уведомления полиции.

Входные данные

Первая строка содержит количество домов n (1n106). Вторая строка содержит n целых неотрицательных чисел a1, a2, ..., an, где ai - количество денег, которое может быть вынесено из i-го дома.

Выходные данные

Выведите максимальную сумму, которую Вы сможете ограбить сегодня вечером без поступления сигнала в полицию.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
5
6 1 2 10 4
Выходные данные #1
16