Can any one explain the approach to solve this problem

problem - D. Flowers

make linear dp

dp[i] = dp[i-1] + dp[i-k]; (red flower at this index + group of k white flowers finish at that index)

then make commulative sum array for this

sum[i] = dp[i] + sum[i-1]

Now you can solve query in O(1)

sum[b]-sum[a-1]

1 Like