В. Префиксы и суффиксы

Условие

В. Префиксы и суффиксы

Дан упорядоченный массив из n нулей. На каждом шаге можно выбрать произвольное количество первых или последних элементов этого массива, и прибавить единицу ко всем выбранным элементам. Можно ли за какое-то количество таких операций достичь указанного состояния массива?

Формат ввода В первой строке целое число 1 ≤ n ≤ 100000 — количество элементов массива.

Во второй строке n целых неотрицательных чисел a1, a2, ..., an через пробел, где ai ≤ 10^18 — требуемые конечные элементы.

Формат вывода Строка "YES", если такое состояние достижимо, и "NO", если недостижимо.

Пример

Ввод [phone]

Вывод YES

Примечание Состояния [phone] можно достичь следующим способом: добавляем единицу к первым трём элементам, получаем [phone] добавляем единицу к последним четырём элементам, получаем [phone] добавляем единицу к последнему элементу, получаем [phone]

Ответ

Массив достижим тогда и только тогда, когда сумма всех положительных падений между соседними элементами не превышает первый элемент. Проверка выполняется за O(n).

Падение a[i−1]−a[i] требует как минимум столько прибавлений префикса, заканчивающегося перед i. Все такие прибавления затрагивают первый элемент, поэтому их сумма не может превышать a[0].

Условие достаточно: каждое падение реализуем соответствующим префиксом, каждый подъём — суффиксом, а остаток a[0] минус сумма падений прибавляем всему массиву. Получаются нужные соседние разности и первый элемент.

n = int(input())
a = list(map(int, input().split()))
drops = sum(max(0, a[i - 1] - a[i]) for i in range(1, n))
print('YES' if drops <= a[0] else 'NO')

Например, [1, 0, 1] достижим, а [0, 1, 0] — нет. Python не переполняет целые числа; в языках с фиксированной разрядностью можно прекращать суммирование сразу после превышения a[0].