Original proposer: admin

The way of painting essentially says “paint periodically with period \(2W\); paint \(W\) cells black and \(W\) cells white.”

For all \(i\), whether to paint cell \(i\) and whether to paint cell \(i+2W\) are the same. Thus, we can merge such cells and supplement cost-\(0\) cells if necessary, to transform the problem as follows:
There are \(2W\) cells on a circle. Each cell has a cost value defined. What is the minimum cost required to paint \(W\) consecutive cells?

We will now consider the transformed problem.

First, calculate the cost of painting \(W\) consecutive cells. Then, apply the sliding window technique: extend one end by one cell, and shrink the other end by one cell. This allows us to compute the total cost of the segment moved by one in \(O(1)\) time. By repeating this, the cost of all ways of painting can be computed in \(O(W)\) time.

Including the transformation cost, the problem has been solved in a total of \(O(N+W)\) time.