CSES - Implementation

Here is the solution. A max-heap tracks the largest values seen, and we adjust when the current element violates non-decreasing order:

function minCost(a)
    n := length of a
    maxHeap := empty max-heap
    cost := 0
    for i from 0 to n-1
        push a[i] to maxHeap
        if maxHeap.top() > a[i] then
            cost := cost + (maxHeap.top() - a[i])
            pop from maxHeap
            push a[i] to maxHeap
    return cost

Each element is pushed once. If it is smaller than the heap top, pop the top, add the cost difference to total, and push the current element again to balance slopes. The heap size grows by at most one per element.

Time: $O(n \log n)$, Space: $O(n)$. This handles value ranges up to $10^9$ that would break standard DP.

Time: $O(n \log n)$. Space: $O(n)$.