length. Вдоль него нанесена шкала от 0 до length, а в массиве marks перечислены отметки, по которым бревно нужно распилить.
Каждый распил делит один кусок на два. Стоимость распила равна длине куска, который в этот момент лежит под пилой. Распилы можно делать в любом порядке, но в итоге бревно должно быть распилено по всем отметкам.
Верните наименьшую возможную суммарную стоимость всех распилов.length=8, marks=[2, 5] → 13
Сначала пилим на отметке 5 (стоимость 8), затем кусок длины 5 на отметке 2 (стоимость 5): всего 13. В обратном порядке вышло бы 8 + 6 = 14.
length=10, marks=[1, 5, 9] → 20
Выгоднее всего начать с середины: 10 за первый распил и по 5 за каждый из двух оставшихся, итого 20.
length=4, marks=[3] → 4
length ≤ 10⁶marks) ≤ min(length − 1, 100)marks[i] ≤ length − 1length=8, marks=[2, 5]
13
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 91 тест на сервере, включая скрытые.