Музыкальный фестиваль

Введём для альбома понятие сжатого альбома , который получается из исходного путём удаления всех элементов, кроме тех, которые являются первыми максимумами на соответствующих им префиксах.

К примеру:

Для альбома $$$[\textbf{1}, \textbf{4}, 4, 3, \textbf{6}, 5, 6]$$$ сжатым будет альбом $$$[1, 4, 6]$$$.

Теперь заметим, что решение исходной задачи сводится к решению этой же задачи, но на сжатых альбомах. Действительно, ответ на них не будет отличаться, ведь если какой-то элемент увеличивал впечатление на обычных альбомах, то он будет увеличивать, если сжать альбомы и наоборот. Далее будет считаться, что предварительно все альбомы были сжаты. Дополнительно введём следующие обозначения $$$K = \sum k_i, C = \max a_{i, j}$$$

1 подгруппа Достаточно просто перебрать порядок в котором Маша будет слушать альбомы, и для каждого порядка посчитать количество впечатления, которое она получит, и взять максимум из этих величин. Решение за $$$O(n! K)$$$

2 подгруппа Заметим, что ответ равен 2, если есть сжатый альбом $$$[1, 2]$$$ или есть сжатые альбомы $$$[1]$$$ и $$$[2]$$$, в ином случае ответ 1. Решение за $$$O(K)$$$

5 подгруппы Отсортируем сжатые альбомы в порядке увеличения последнего числа. Заметим, что если Маша послушала альбом с номером $$$i$$$, то все альбомы с номерами меньше дадут 0 единиц впечатления. Теперь можно посчитать следующую динамику. $$$dp_i$$$ — количество впечатления, при условии, что Маша послушала последним $$$i$$$-й альбом. При пересчёте $$$dp_i$$$ через $$$dp_j$$$ надо посчитать количество, элементов в $$$i$$$-м альбоме, что они больше, чем наибольший в $$$j$$$-м. Решение за $$$O(n^2 \log K)$$$, если использовать бинарный поиск.

3 подгруппа Существует не более чем $$$2^C$$$ различных вариантов сжатых альбомов. Тогда удалив одинаковые сжатые альбомы и, применив решение для $$$5$$$-й подзадачи, можно получить решение за $$$O(4^C \log K)$$$.

4 подгруппа Введём $$$dp_c$$$ — максимум впечатления, которое можно получить, если бы не было альбомов таких, что в них есть элементы большие, чем $$$c$$$. Тогда, $$$dp_c$$$ равно либо $$$dp_{c-1}$$$, либо можно добавить ещё элемент или два, если $$$c$$$ является наибольшим элементом для какого-то альбом. Тогда для всех сжатых альбомов, можно пересчитаться через значение $$$dp$$$ в точке перед первым элементом альбома, либо через $$$c - 1$$$. Таким образом для пересчёта достаточно знать для каждого $$$c$$$ какие альбомы закончились в этом индексе, а так же для каждого альбома его первый элемент. Решение за $$$O(K)$$$

Полное решение Обобщим идею предыдущих подгрупп. Для каждого значения $$$c$$$ запомним индексы альбомов, которые содержат элемент равный $$$c$$$. Идём в порядке увеличения $$$c$$$, поддерживаем для каждого альбома значение $$$dp_i$$$ — максимум впечатления, который можно получить если бы не было элементов больших $$$c$$$ и Маша послушала последним $$$i$$$-й альбом. Пусть, для очередного $$$c$$$ существует альбом $$$i$$$, что в нём есть песня с крутостью $$$c$$$. Тогда $$$dp_i$$$ будет максимумом из $$$dp_i + 1$$$ и значения по всем $$$dp_j + 1$$$, таких, что наибольший элемент в $$$j$$$-м альбоме меньше чем рассматриваемый элемент $$$i$$$-го, так как она могла послушать этот трек, либо следующим в этом альбоме, либо после того, как послушала какой-то другой альбом целиком. Заметим, что можно хранить максимальный ответ по всем альбомам, для которых наибольшее значение в них меньше $$$c$$$ и пересчитываться через это значение. В таком случае, получится решение за $$$O(K + C)$$$.