Expert.
Put your skills to the test.

Problem summary

Change sequence elements by incrementing or decrementing one at a time. Find the minimum total number of operations needed to make the sequence nondecreasing.

Constraints

1 ≤ n < 100,000; 1 ≤ ai < 10,000.

Worked example

Official sample, transcribed with whitespace restored from the PDF.

5
2 6 4 3 2

5

Solution analysis

1. We minimize the sum of absolute changes, subject to the final sequence being nondecreasing. Let F_i(x) be the minimum cost for the first i elements when their final element is at most x. This is a convex, nonincreasing, piecewise-linear function. A max-heap compactly represents its breakpoints.
2. Maintain a constant cost C and a multiset H such that F_i(x)=C+Σ(h in H)max(0,h−x). For a new value a, insert a. If the maximum breakpoint h exceeds a, add h−a to C, remove one copy of h, and insert another copy of a. Otherwise no correction is needed. This is the exact update for F_i(x)=min(y≤x)(F_(i−1)(y)+|y−a|). The unrestricted minimum is C, obtained to the right of all breakpoints.
3. For 2,6,4,3,2, the heap updates add costs 0,0,2,1,2, totaling five. One optimal final sequence is 2,4,4,4,4: the changes cost 0+2+0+1+2. The algorithm computes the cost without reconstructing the final sequence.

Why it works

The empty prefix has F_0(x)=0. For a multiset of hinge functions max(0,h−x), adding |a−x| and taking the minimum over endpoints at most x leaves the stated hinge representation: if the largest old breakpoint is at most a, append breakpoint a; otherwise the decreasing and increasing slopes cancel between a and that largest breakpoint, raising the constant by h−a and replacing h with two copies of a. This also follows by comparing slopes on each interval between breakpoints. Induction establishes the invariant. As x tends above every breakpoint, all hinge terms vanish, so C is exactly the unrestricted optimal nondecreasing adjustment cost.

Watch out. The target is nondecreasing, not strictly increasing. A correction inserts a second copy of the new value. The total cost should use 64-bit arithmetic.

An independently written complete program with standard headers.

// Key idea: The empty prefix has F_0(x)=0. For a multiset of hinge functions max(0,h−x), adding |a−x|
// and taking the minimum over endpoints at most x leaves the stated hinge representation: if the
// largest old breakpoint is at most a, append breakpoint a; otherwise the decreasing and increasing
// slopes cancel between a and that largest breakpoint, raising the constant by h−a and replacing h
// with two copies of a.
#include<iostream>
#include<queue>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    priority_queue<int>breakpoints;
    long long cost=0;
    for(int i=0;i<n;++i){
        int value;
        cin>>value;
        breakpoints.push(value);
        if(breakpoints.top()>value){
            cost+=breakpoints.top()-value;
            breakpoints.pop();
            breakpoints.push(value);
        }
    }
    cout<<cost<<'\n';
}