AliKingspress

Для начала решим задачу с использованием O(x·n) памяти, а затем придумаем, как это решение соптимизировать.

Посчитаем стандартную динамику dpx, n — минимальное количество дней, требуемое для получения x бонусов, учитывая то, что сейчас мы заходили n дней подряд. Переходы в этой динамике довольно логичные и описаны в условии: и (во втором случае мы считаем, что после пропуска дня нет смысла ждать еще несколько дней, поэтому сразу авторизируемся в следующий день)

Однако это решение использует O(x·n) памяти, что при данных ограничениях превышает 400 мегабайт и не укладывается в лимит по памяти. Чтобы устранить это, применим стандартный прием оптимизации памяти в динамике. Заметим, что из состояния (x, n) мы переходим только в те состояния (x', n'), где x - x' <  = 103 (ограничение на элемент массива a). Тогда мы можем хранить не все x строк в матрице dp, а только последние 1000 из них, это соптимизирует нашу память в 1000 раз и позволит уложиться в лимит по памяти.