学步园

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#define iinf 0x7f7f7f7f
#define linf 1000000000000000000LL
#define dinf 1e200
#define eps 1e-11
#define lng long long
#define sqr(a) ((a)*(a))
#define pii pair<int,int>
#define X first
#define Y second
#define pi 3.14159265359
#define cc(i,j) memset(i,j,sizeof(i))
#define two(x)          ((lng)1<<(x))
#define mod  9901
#define pmod(x,y) (x%y+y)%y
using namespace std;
typedef vector<int>  vi;
typedef vector<string>  vs;
template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;}
template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;}
template<class T> inline T Min(T x,T y){return (x>y?y:x);}
template<class T> inline T Max(T x,T y){return (x<y?y:x);}
template<class T> T Abs(T a){return a>0?a:(-a);}
int n,k;
int  a[3000];
int  dp[2222][1111];
int main()
{
    while(scanf("%d%d",&n,&k)==2)
{
    for(int i=1;i<=n;++i)
    scanf("%d",a+i);
    sort(a+1,a+1+n);
    dp[0][0]=0;
   for(int i=2;i<=n;++i)
   {
      for(int j=1;j<i/2;++j)
       dp[i][j]=Min(dp[i-2][j-1]+sqr(a[i]-a[i-1]),dp[i-1][j]);
       int j=i/2;
       if(j*2==i)
             dp[i][j]=dp[i-2][j-1]+sqr(a[i]-a[i-1]);
             else
        dp[i][j]=Min(dp[i-2][j-1]+sqr(a[i]-a[i-1]),dp[i-1][j]);
   }
   printf("%d\n",dp[n][k]);
}
    return 0;
}