Cacher is the code snippet organizer for pro developers

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

typedef long long LL;
const int INF=0x3f3f3f3f;
const int MAXN=1e3+5;
const int MAXM=1e5+5;
const int mod=1e9+7;

int n,m;
int x[MAXN],sum[MAXN],dp[MAXN][MAXN];

bool cmp(const int& a,const int& b){
    return a>b;
}

int main(){
    int aa; scanf("%d",&aa);
    while(aa--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&x[i]);
        sort(x+1,x+n+1,cmp);
        sum[0]=0;
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i];
        memset(dp,INF,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                for(int k=0;k<i;k++)
                    dp[i][j]=min(dp[i][j],dp[k][j-1]+i*(sum[i]-sum[k]));
        printf("%.4f\n",1.0*dp[n][m]/sum[n]);
    }
    return 0;
}