The problem can be rephrased as follows:

We will pick one or more days among \(N\) days and make them holidays. Making day \(i\) a holiday incurs a cost of \(A_i\). No two adjacent holidays must have two or more weekdays in between.

When the first and last holidays are on day \(S\) and \(T\), respectively, find the minimum cost to have \(T-S \geq K-1\).

We only have to consider the case where \((T-S)\) equals \((K-1)\) or \(K\), in which case the minimum cost can be found as the minimum value of \(\mathrm{dp}_1[K]\) among the DP computed for \(l=1,2,\dots,N-K\). Here, \(\mathrm{INF}\) is a sufficiently large value (for example, \(10^{18}\) under the constraints of the problem), and \(A_0=\mathrm{INF}\).

• \(\mathrm{dp}_0[0]=0,\mathrm{dp}_1[0]=A_{l-1}\).
• \(\mathrm{dp}_0[i]=\mathrm{dp}_1[i-1],\mathrm{dp}_1[i]=\min(\mathrm{dp}_0[i-1],\mathrm{dp}_1[i-1])+A_{l+i-1}\), for each \(1\leq i\leq K\).

However, computing the DP above for all \(l\) costs \(\Theta(KN)\) time.

If we define a mapping \(f_a\) as \(f_a(x,y)=(y,\min(x,y)+a)\), the DP transition above can be represented as

\[(\mathrm{dp}_0[i],\mathrm{dp}_1[i])=f_{A_{l+i-1}}(\mathrm{dp}_0[i-1],\mathrm{dp}_1[i-1]),\]

so it is sufficient to evaluate the composition \(f_{A_{l+K-1}}\circ\cdots\circ f_{A_{l+1}}\circ f_{A_{l}}\). Any composition of \(f_{*}\) can be represented in the form \((\min(x+a,y+b),\min(x+c,y+d))\), so it can be evaluated by managing values \(a,b,c,d\), and using a data structure that supports segment-product retrieval.

Alternatively, it can be interpreted as a matrix product of min-plus algebra:

\[ \begin{pmatrix}\mathrm{dp}_0[K]\\\mathrm{dp}_1[K]\end{pmatrix} = \begin{pmatrix}\mathrm{INF}&0\\A_{l+K-1}&A_{l+K-1}\end{pmatrix} \cdots \begin{pmatrix}\mathrm{INF}&0\\A_l&A_l\end{pmatrix} \begin{pmatrix}\mathrm{dp}_0[0]\\\mathrm{dp}_1[0]\end{pmatrix}. \]

If we use Sliding Window Aggregation (SWAG) for segment-product computation, the problem can be solved in \(O(N)\) time; if we use a segment tree, it can be solved in \(O(N\log N)\) time.

Sample code (C++, SWAG) Sample code (C++, segment tree)

Also, the problem can be solved by splitting the entire segment into blocks of length \(K\), computing prefix- and suffix- products for each block, and combining the results for adjacent blocks. This also runs in \(O(N)\) time.

Sample code (PyPy, split into blocks)