Распределение энергии по делам

У вас расписан день: дела идут в фиксированном порядке, у i-го дела ценность values[i]. Утром у вас max_energy единиц энергии — это и запас, и потолок. На каждое дело вы тратите любое целое неотрицательное количество энергии, но не больше, чем есть сейчас; выгода от дела — его ценность, умноженная на потраченную энергию. После каждого дела вы восстанавливаете regain единиц, но энергии никогда не бывает больше max_energy (лишнее пропадает).

Верните наибольшую суммарную выгоду за день. Ограничения: 1 ≤ max_energy, regain ≤ 10⁶, дел от 1 до 10⁴, ценности от 1 до 10⁴.

Пример: 5, 2, [1, 2] → 12 (2 единицы на первое дело, восстановиться до 5 и потратить их на второе).

Источник: Coding Competitions Archive, codejam/2013/round_1a/manage_your_energy · © Google LLC · Apache-2.0 · условие переведено и дополнено