Minimum cost to clear a binary array with k-wide windows

A packaging line tracks a row of n units, each built as one of two variants: variant A is written 0 and variant B is written 1. You need to convert every unit to variant A.

You are given the binary array product and an integer k (1 <= k <= n). One operation works like this:

1. Pick a contiguous block of exactly k positions, [l, l + k - 1].
2. Pay the current sum of product over that block, measured before anything changes.
3. Pick one position in the block that holds a 1 and set it to 0. The block must contain at least one 1.

Return the minimum total cost to make every element 0.

def min_conversion_cost(product: list[int], k: int) -> int: ...

Constraints

• 1 <= n <= 2 * 10^5
• product[i] is 0 or 1
• 1 <= k <= n
• The answer can exceed 32 bits.

Example 1

product = [1, 1, 1], k = 2
output  = 4

Choose block [0, 1] (cost 2) and clear index 1, which gives [1, 0, 1]. Now block [0, 1] costs 1 to clear index 0, and block [1, 2] costs 1 to clear index 2. The total is 4. Clearing index 0 first would cost 2 + 2 + 1 = 5.

Example 2

product = [0, 1, 1, 1, 1, 0], k = 4
output  = 7

Every block of length 4 holds at least 3 ones. Clearing the three ones of block [0, 3] while paying for that block each time costs 3 + 2 + 1. The last 1 then costs 1.

Part 2 (if time allows): return one optimal sequence of operations as (l, index_cleared, cost) triples.