Що обмежує робота насправді. Коробки лежать у робочому контейнері відсортованими за зростанням, і брати можна лише верхню. Коробку в прокрастинаційний контейнер можна лише прибрати — назад її не дістати. Отже коробка з номером потрапляє на полицю тільки після того, як усі менші номери вже або розставлені, або викинуті. Висновок:
номери розставлених коробок утворюють зростаючу послідовність.
Друге обмеження — геометричне. За день робот проходить доріжку разів, щоразу розвертаючись. Тому позиції полиць, на які він кладе коробки, зростають під час непарного проходу й спадають під час парного.
Переформулювання. Нехай — позиція полиці з номером на доріжці. Треба вибрати якнайдовшу зростаючу послідовність номерів v_1 < v_2 < \ldots < v_m так, щоб послідовність \mathrm{pos}[v_1], \ldots, \mathrm{pos}[v_m] розбивалася щонайбільше на монотонних шматків, які по черзі зростають і спадають. При K = 1 це рівно задача про найдовшу зростаючу підпослідовність перестановки — і саме так її й треба розв'язувати, лише в шарах.
Динаміка. Обробляємо проходи k = 1, 2, \ldots, K, а всередині кожного — значення від до (тобто в тому самому порядку, у якому коробки виходять зі стосу). Для поточного проходу тримаємо дерево Фенвіка на максимум над позиціями:
Другий варіант — це перехід на новий прохід: там жодних обмежень на позицію немає (робот розвернувся й може почати де завгодно), тому достатньо тримати масив — найкращий результат по всіх попередніх проходах серед значень .
Для парних проходів позиції мають спадати. Щоб не писати другий варіант коду, індексуємо дерево Фенвіка з протилежного кінця: замість позиції беремо N + 1 - q. Тоді «менша позиція» знову означає «префікс», і код той самий.
Наприкінці кожного проходу оновлюємо M[v] \leftarrow \max(M[v], G[v]), де — префіксний максимум по цьому проходу. Відповідь — .
Складність — \mathcal{O}(K \cdot N \log N), що за N \le 10^5 і K \le 100 цілком проходить. Дерево Фенвіка на максимум із повним переініціалізуванням на кожному проході — додатково, це дрібниця.