Proficient.
Put your skills to the test.

Problem summary

A nondecreasing sequence of heights describes N unit path sections. Changing a section height by one costs 1; placing an elevator between adjacent sections costs K. Adjacent unequal final heights require an elevator. Minimize total cost; the first section’s height is unrestricted.

Constraints

N≤100000; 3≤K≤10^9; heights are nonnegative integers at most 10^9.

Worked example

An independently prepared example for this explanation.

5 3
1 2 8 9 9

5

Solution analysis

1. Elevators partition the path into constant-height blocks. A block [l,r] is optimally flattened to a median. Because heights are already sorted, its median index is (l+r)/2; prefix sums give the sum of absolute deviations in O(1).
2. Let dp[i] be the minimum cost for the first i sections. Set dp[0]=−K and use dp[i]=min over j<i of dp[j]+K+cost(j+1,i). The sorted absolute-deviation cost is Monge: for older split j and newer split k, the newer split’s relative cost can only improve as the right endpoint grows.
3. Maintain candidate split points in a deque, each with the first future endpoint where it is optimal. A new candidate eliminates worse candidates at the back; otherwise binary-search its first crossover with the last candidate. Front intervals expire as i increases. For 1,2,8,9,9, flatten the first two at cost 1 and the last three at cost 1, with one elevator costing 3, total 5.

Why it works

Median flattening minimizes each block’s absolute deviations, so the partition recurrence is exact. For a sorted interval, extending its right endpoint adds the new height minus an appropriate central height; that central height is no smaller for a later left endpoint. Hence cost(j+1,r)−cost(k+1,r) is nondecreasing in r for j<k. Candidate preference changes at most once, so binary-searched crossover intervals form the exact lower envelope. Deleting a candidate whose whole interval is dominated and querying the current front therefore preserves the DP minimum at every step.

Watch out. Use 64-bit prefix sums and costs. Set dp[0]=−K to avoid charging an elevator before the first block. Candidate comparisons must use only future endpoints where both blocks are nonempty.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
struct Candidate{
    int split;
    int start;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int count;
    long long elevator;
    cin>>count>>elevator;
    vector<long long>height(count+1,0),prefix(count+1,0),dp(count+1,0);
    for(int i=1;i<=count;i++){
        cin>>height[i];
        prefix[i]=prefix[i-1]+height[i];
    }
    auto blockCost=[&](int left,int right){
        int middle=(left+right)/2;
        return height[middle]*(middle-left+1)-(prefix[middle]-prefix[left-1])+prefix[right]-
            prefix[middle]-height[middle]*(right-middle);
    };
    dp[0]=-elevator;
    auto value=[&](int split,int end){
        return dp[split]+elevator+blockCost(split+1,end);
    };
    deque<Candidate>envelope;
    envelope.push_back({0,1});
    for(int end=1;end<=count;end++){
        while(envelope.size()>=2&&envelope[1].start<=end){
            envelope.pop_front();
        }
        dp[end]=value(envelope.front().split,end);
        if(end==count){
            continue;
        }
        int first=end+1;
        while(!envelope.empty()){
            int compareAt=max(first,envelope.back().start);
            if(value(end,compareAt)<=value(envelope.back().split,compareAt)){
                envelope.pop_back();
            }
            else{
                break;
            }
        }
        if(envelope.empty()){
            envelope.push_back({end,first});
        }
        else if(value(end,count)<=value(envelope.back().split,count)){
            int low=max(first,envelope.back().start);
            int high=count;
            // The later split becomes preferable at most once.
            while(low<high){
                int middle=(low+high)/2;
                if(value(end,middle)<=value(envelope.back().split,middle)){
                    high=middle;
                }
                else{
                    low=middle+1;
                }
            }
            envelope.push_back({end,low});
        }
    }
    cout<<dp[count]<<'\n';
}