#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/slope-trick/cses-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/slope-trick/cses-implementation

Repovive

CSES - Implementation - Slope Trick | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

CSES - Implementation

Max-heap solution

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)$ .