Тихие кварталы

Ночной дрон летит над прямой улицей из n кварталов. В i-м квартале можно забрать трофеи на сумму a_i.

Но система наблюдения устроена так: если забрать трофеи в двух соседних кварталах, тревога сработает. Дрон хочет собрать как можно больше и остаться незамеченным.

Обратите внимание: суммы могут не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битные целые. В Python это не проблема.

Формат ввода

• В первой строке целое число n.
• Во второй строке n целых чисел a_1, a_2, ..., a_n.

Формат вывода

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

Ограничения

• 2 ≤ n ≤ 35000
• 0 ≤ a_i ≤ 10^9

Пример

Ввод:

5
2 7 9 3 1

Вывод:

12

(например, можно взять кварталы 1, 3 и 5: 2 + 9 + 1 = 12)

Ключевое наблюдение: выбор в квартале i влияет только на квартал i-1 (соседний). Значит, чтобы посчитать лучший результат для первых i кварталов, достаточно знать лучший результат для первых i-1 и i-2.

Приём: динамическое программирование (ДП) по префиксу. Оно работает, потому что у задачи есть «оптимальная подструктура»: оптимальный набор на первых i кварталах строится из оптимальных наборов на меньших префиксах.

Обозначим dp[i] — максимальная сумма, которую можно собрать среди кварталов 1..i без соседей. Тогда есть два варианта для i-го квартала:

• не берем i: получаем dp[i-1]
• берем i: тогда i-1 брать нельзя, получаем dp[i-2] + a[i]

Значит, переход: dp[i] = max(dp[i-1], dp[i-2] + a[i]).

План решения:

• Считать n и массив a.
• Завести базу: dp[0] = 0 (ничего не взяли), dp[1] = a[1].
• Для i = 2..n посчитать dp[i] по формуле выше.
• Ответ — dp[n].
• Чтобы не хранить весь dp, держите только два последних значения (для i-1 и i-2) и обновляйте их по циклу.

Сложность: O(n) по времени, память O(1) (или O(n), если хранить весь dp).

Частая ошибка: неверная база и индексация (особенно при переходе от 1-индексации в условии к 0-индексации в Python). Убедитесь, что для i=1 и i=2 формулы работают корректно.