堆/贪心
一共N-1个元素……用堆维护最大值，取了第x个元素以后，插入v[x-1]+v[x+1]-v[x]这个元素，如果再取这个新元素就表示不取x，而取x-1和x+1……大概就是这种“带反悔”的思路吧……
已经不会写堆了TAT，膜拜了lyd神犇
/**************************************************************
Problem: 1150
User: Tunix
Language: C++
Result: Accepted
Time:428 ms
Memory:3224 kb
****************************************************************/ //BZOJ 1000
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std; int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}
return v*sign;
}
typedef long long LL;
const int N=,INF=~0u>>;
/*******************tamplate********************/
int f[N],a[N],pre[N],next[N],v[N];
int n,m,ans,p;
void up(int p){
while(p>)
if(a[f[p]]<a[f[p>>]]){
swap(f[p],f[p>>]);
swap(v[f[p]],v[f[p>>]]);
p>>=;
}
else break;
}
void down(int l,int r){
int t=l<<;
while(t<=r){
if (t<r && a[f[t]]>a[f[t+]]) t++;
if (a[f[l]]>a[f[t]]){
swap(f[l],f[t]);
swap(v[f[l]],v[f[t]]);
l=t,t=l<<;
}
else break;
}
}
void insert(int x){
f[++p]=x; v[x]=p;
up(p);
}
void erase(int x){
f[v[x]]=f[p]; v[f[p]]=v[x]; p--;
up(v[x]); down(v[x],p);
}
int main(){
n=getint(); m=getint();
F(i,,n) a[i]=getint();
F(i,,n-){
a[i]=a[i+]-a[i],next[i]=i+,pre[i+]=i;
insert(i);
}
F(i,,m){
int x=f[]; ans+=a[x];
if(pre[x]== && next[x]==n) break;
if(pre[x]==){
erase(x),erase(next[x]);
pre[next[next[x]]]=;
}else if(next[x]==n){
erase(x),erase(pre[x]);
next[pre[pre[x]]]=n;
}else{
erase(x),erase(pre[x]),erase(next[x]);
a[x]=a[pre[x]]+a[next[x]]-a[x];
insert(x);
pre[x]=pre[pre[x]]; next[pre[x]]=x;
next[x]=next[next[x]]; pre[next[x]]=x;
}
}
printf("%d\n",ans);
return ;
}