分治建图

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define int long long
#define maxn 800010
#define maxm 800010
int cnt,n,m,s,t,head[maxn],nxt[maxm],to[maxm],cost[maxm],w[maxm];
const int INF=0x3f3f3f3f3f3f3f3f;
void _add(const int& u,const int& v,const int& c,const int& f){
	to[cnt]=v;cost[cnt]=c;w[cnt]=f;nxt[cnt]=head[u];head[u]=cnt++;
}
void add(const int& u,const int& v,const int& c,const int& f){
	_add(u,v,c,f);
	_add(v,u,-c,0);
}
int h[maxn];
struct node{
	int x,d;
	bool operator < (const node& x)const{
		return d>x.d;
	}
	node(const int& xx,const int& dd):x(xx),d(dd){}
};
int flow[maxn],pre[maxn],dis[maxn];
std::vector<node> q;
#define pop() std::pop_heap(q.begin(),q.end()),q.pop_back()
bool dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	pre[s]=-1;
	dis[s]=0;
	flow[s]=INF;
	while(!q.empty())q.pop_back();
	q.push_back(node(s,0));
	while(!q.empty()){
		int x;
		while(!q.empty()&&q.at(0).d!=dis[q.at(0).x])pop();
		if(q.empty())return false;
		x=q.at(0).x;pop();
		if(x==t)return true;
		for(int i=head[x];~i;i=nxt[i])
			if(w[i]&&dis[to[i]]>dis[x]+cost[i]+h[x]-h[to[i]]){
				dis[to[i]]=dis[x]+cost[i]+h[x]-h[to[i]];
				q.push_back(node(to[i],dis[to[i]]));
				std::push_heap(q.begin(),q.end());
				pre[to[i]]=i;
				flow[to[i]]=flow[x]<w[i]?flow[x]:w[i];
			}
	}
	return false;
}
int ansflow,anscost;
int a[1010],tot,p[1010][2],ww;
void build(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1,num=0;
	build(l,mid),build(mid+1,r);
	static int b[1010];
	for(int i=l;i<=r;i++) b[++num]=a[i];
	std::sort(b+1,b+num+1);
	num=std::unique(b+1,b+num+1)-b-1;
	for(int i=1;i<num;i++){
		add(tot+i,tot+i+1,b[i+1]-b[i],INF);
		add(tot+i+1,tot+i,b[i+1]-b[i],INF);
	}
	for(int i=l;i<=r;i++){
		int pos=std::lower_bound(b+1,b+num+1,a[i])-b;
		if(i>mid)add(p[i][0],tot+pos,0,1);
		else add(tot+pos,p[i][1],0,1);
	}
	tot+=num;
}
signed main(){
	memset(head,0xff,sizeof(head));
	scanf("%lld%lld",&n,&ww);
	s=++tot,t=++tot;
	for(int i=1;i<=n;i++)scanf("%lld",a+i),p[i][0]=++tot,p[i][1]=++tot;
	for(int i=1;i<=n;i++)add(s,p[i][0],0,1),add(p[i][0],t,ww,1),add(p[i][1],t,0,1);
	build(1,n);
	while(dijkstra()){
		for(int i=pre[t];~i;i=pre[to[i^1]]){
			w[i]-=flow[t];
			w[i^1]+=flow[t];
		}
		for(int i=1;i<=tot;i++)h[i]=std::min(h[i]+dis[i],INF);
		ansflow+=flow[t];
		anscost+=flow[t]*h[t];
	}
	printf("%lld\n",anscost);
	return 0;
}