思路是记录 $f_{i,j}$ 为前 $i$ 头奶牛，当前这组已经放了 $j$ 头奶牛可以达到的技能水平之和的最大值。

#include <bits/stdc++.h>

#define int long long 

using namespace std;

const int N=1e4+10;
const int K=1e3+10;

int f[N][K];//当前是在元素i，当前组有j组奶牛的可以达到的技能水平之和的最大值 
int n,k;
int a[N];
int st[N][21];
int lg[N];
int g[N];

int query(int l,int r){
	if(r==l) return st[l][0];
	if(r<l) return 0;
	int len=r-l+1;
	int k=lg[len];
	return max(st[l][k-1],st[r-(1<<(k-1))+1][k-1]);
}
 
signed main() {
	cin>>n>>k;
	lg[0]=-1;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		st[i][0]=a[i];
		lg[i]=lg[i>>1]+1;
	}	
	for(int j=1;j<=20;++j){
		for(int i=1;i+(1<<j)<=n;++i){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=k;++j){
			if(j==1) {
				f[i][j]=g[i-1];
				f[i][j]+=a[i];
			}
			else{
				f[i][j]=f[i-1][j-1];
				f[i][j]-=query(max(1ll,i-1-j+1),i-1)*(j-1);
				f[i][j]+=query(max(1ll,i-1-j+1),i)*j;
			}
			g[i]=max(g[i],f[i][j]);
		}
	}
	int maxx=INT_MIN;
	for(int i=1;i<=n;++i){
		maxx=max(maxx,f[n][i]);
	}
	cout<<maxx<<"\n";
	return 0;
}