# 02.02.2026 [3013. Divide an Array Into Subarrays With Minimum Cost II]
Min sum of k splits at max d distance #hard #sliding_window #heap
02.02.2026
3013. Divide an Array Into Subarrays With Minimum Cost II hard blog post substack youtube
Join me on Telegram
Problem TLDR
Min sum of k splits at max d distance #hard #sliding_window #heap
Intuition
Didn’t solve.
// take first
// select k-1 min-sum values at dist
//
// ***********
// * * *
//
// move (k-1) pointers?
//
// binarysearch?
//
// binarysearch+dp? dp answers for sum: canSplit[i]
// still should be minSplit[i] O(n^2)
// no other ideas, lets try dp, inner cycle is d, O(nkd)
// obviously deadend tle
// somehow stuck with brute-force dp
// looks like i didn't understood the description
// dist is not between splits
// it is between second and last
//
// let's go to hints
//
// sliding window + heap + heap
//
// *|**m*|********
// i-d i
//
// let's give up at 50 minutes
Maintain sliding window of d
Put k-1 best values in one sorted container (TreeSet of n[i],i)
Remove overflows and d+1-distant values.
Keep still-in-window values in a second storage container
Balance when d+1-distant value has been removed
Approach
there is also a BIT solution (ask ai): sort distinct values, keep BIT-arrays of counts and sums
Complexity
Time complexity: $$O(nlogn)$$
Space complexity: $$O(n)$$
Code
// 533ms
fun minimumCost(n: IntArray, k: Int, d: Int): Long {
var sum = 0L; val c = compareBy<Int>({n[it]},{it})
val q = TreeSet(c); val s = TreeSet(c)
return (1..<n.size).minOf { i ->
q += i; sum += n[i]
if (q.size >= k) { val j = q.pollLast(); sum -= n[j]; s += j }
if (i-d-1 > 0 && !s.remove(i-d-1) && q.remove(i-d-1)) {
sum -= n[i-d-1]; val j = s.pollFirst(); sum += n[j]; q += j
}
if (i-d-1 >= 0) sum else 1L shl 60
} + n[0]
}