We can solve it without dp too in O(N^2) using contribution to total sum trick, consider an arbitary subarray [l,r] assume this is a single segment and there are separators between Ar & Ar+1 , Al-1, Al , so now we have k-3 separators left to place in left segment and right segment and multiply this product by avaliable gaps in both left and right combined let this number be g , ans+=product*gCk-3 do this for all subarrays and u get the answer.