Problem: Example

Input

4 3
1 3 4 7


Output

6

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

int N,K;
int dp[2][1001][1001];
int dm[2][1001][1001];

int a[1000];

int main(){
  scanf("%d %d",&N,&K);
  for(int i=0;i<N;i++)scanf("%d",&a[i]);
  sort(a,a+N);
  
  fill( (int*)dp[0], (int*)dp[1], 1e9);


  int ans=1e9;
  
  for(int T=1;T<=K;T++){
    int t=T%2;
    int u=1-t;

    fill( (int*)dp[t], (int*)dp[t+1], 1e9);
    for(int i=0;i<N;i++){
      dp[0][i][i+1]=0;
      dp[1][i][i+1]=0;
    }
    
    for(int w=2;w<=N;w++){
      for(int i=0;i+w<=N;i++){
        int j=i+w;
        int si=i+1;
        int ti=j-1;

        if(w>2){
          si=dm[t][i][j-1];
          ti=dm[t][i+1][j];
        }
        
        for(int k=si;k<=ti;k++){
          if(dp[t][i][j] > dp[u][i][k]+dp[u][k][j]+a[j-1]-a[k-1]){
            dp[t][i][j]=dp[u][i][k]+dp[u][k][j]+a[j-1]-a[k-1];
            dm[t][i][j]=k;
          }
        }

        if(i==0&&j==N)ans=min(ans,dp[t][i][j]);
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}