yep it was harder..

I solved it with some maths intuition. After a lot of case work I found that

For a sequence of $$${[L, R]}$$$ should be good if and only if.

$$${A_i + A_{i - k} + A_{i - 2 * k} + .... A_p - A_{i - 1 - k} - A_{i - 1 - 2 * k} - .... A_{p-1} = 0}$$$

where $$${p < L}$$$ and $$${L \le p + k}$$$.

for all $$$i$$$, $$${R - k + 2 \le i \le R}$$$

My Submission

According to Kenkoooo Atcoder Problems, ABC288D may be the second Problem D (in 8 problems rounds) that difficulty is above 1600. It is even harder than the first one ABC227D. But I think that ABC288 is easier than ABC227 on the whole.

Could you please explain the burnside lemma solution?

The key observation in $$$E$$$ is that if we bought $$$2$$$ items $$$i$$$ and $$$j$$$ ($$$i<j$$$), then for $$$i$$$ it will not matter whether we buy it before or after $$$j$$$, but for $$$j$$$ it will matter because if we bought $$$j$$$ first, we would use $$$C[j]$$$, otherwise we would use $$$C[j-1]$$$.

So let $$$dp[i][j]$$$ be the least amount of money we can spend if we start from item $$$i$$$ and we bought $$$j$$$ items with indexes less than $$$i$$$. If item $$$i$$$ is not in $$$X$$$ we can consider the option of not buying it. For the other option of buying it, we can buy it first before buying any of the $$$j$$$ items (will use $$$C[i]$$$), or we can buy it after buying $$$1$$$ of the $$$j$$$ items (will use $$$C[i-1]$$$), and so on.

So, we can have an array $$$mins$$$ where $$$mins[i][j]$$$ is the smallest $$$C[k]$$$ for $$$j\le k\le i$$$. So when we want consider buying item $$$i$$$ if we bought $$$j$$$ items with indexes less than $$$i$$$, we can set $$$dp[i][j] = min(dp[i][j], a[i]+mins[i][i-j]+dp[i+1][j+1])$$$.

Submission

It's exactly 2000