I know how to solve this in O(N^2*k)

We will solve it with dp, dp[A][B] denotes the minimal cost to cover the first A buildings with B atms.

Before the general solution for all K, let's think about the solution with K=1. If K=1, than it's optimal to place the atm at the location of the middle — a[N/2]. We can prove this because if there are L buildings to the left of the atm and R buildings to the right, then the cost of moving it right increases by L-R. Since L=R in the middle, moving it right will make the result the same, until we pass a building, from then on L > R, and the cost will only increase.

This approach can be used to compute the cost of covering a subarray of our buildings with one atm. For a subarray L-R, and the middle = M, the cost of covering it with one atm will be sum_of_positions[M...R] — M*number_of_buildings[M...R] + M*number_of_buildings[L...M] — sum_of_positions[L...M]. The sum of positions on a segment can be computed with prefix sums.

Now that we know how to compute the cost of a segment with one atm on it, let's get to the dp transitions: dp[A][B] is the minimum of all dp[X][B-1] + cost_of_segment[X+1...A] for all X < A.

We have N*K states, and each we know how to compute each in O(n) so the overall time complexity will be: O(N^2*K)

Here's some code:

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

const int MAXN=5e2+10;
const long long inf=1e18+2137;

long long dp[MAXN][MAXN];
long long a[MAXN];
long long ps[MAXN];

long long sum(int l,int r)
{
    return ps[r]-ps[l-1];
}

long long seg_ans(int l,int r)
{
    int m=(l+r)/2;
    return sum(m,r)-a[m]*(long long)(r-m+1)-sum(l,m)+a[m]*(long long)(m-l+1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        ps[i]=ps[i-1]+a[i];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++)
            dp[i][j]=inf;
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
            for(int l=0;l<i;l++)
                dp[i][j]=min(dp[i][j],dp[l][j-1]+seg_ans(l+1,i));
    cout<<dp[n][k];
}