#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;
int sum_cache[100][101];
int result_cache[11][101];

int min_square_sum(int start, int end) {
    int sum = 0;
    int& square_sum = sum_cache[start][end];
    if(square_sum != -1) {
        return square_sum;
    }
    square_sum = 0;
    for(int i=start; i<end; i++) {
        sum += arr[i];
    }
    int average = int(round(double(sum) / (end - start)));
    for(int i=start; i<end; i++) {
        square_sum += (average - arr[i]) * (average - arr[i]);
    }
    return square_sum;
}

int quantinize(int n, int s, int start) {
    if(s == 1)
        return min_square_sum(start, n);
    int& result = result_cache[s][start];
    if(result != -1)
        return result;
    result = 987654321;
    for(int i=start+1; i<=n-s+1; i++) {
        result = min(result, min_square_sum(start, i) + quantinize(n, s-1, i));
    }
    return result;
}

int main() {
    int c;
    cin >> c;
    for(int i=0; i<c; i++) {
        int n, s;
        cin >> n >> s;
        for(int j=0; j<n; j++) {
            int a;
            cin >> a;
            arr.push_back(a);
        }
        sort(arr.begin(), arr.end());
        memset(sum_cache, -1, 100*101*sizeof(int));
        memset(result_cache, -1, 11*101*sizeof(int));
        cout << quantinize(n, s, 0) << endl;
        arr.clear();
    }
}

덩어리를 나눈 것에 대한 해도 캐쉬를 사용하고, 부분 집합의 최소 제곱 합을 구하는 부분에서도 캐쉬를 사용하게끔 해서 구현하였습니다.
책의 해답과는 부분 집합의 제곱 합을 구하는 부분의 아이디어가 다르고, 덩어리를 남지 않게 나눈다는 부분만 다른 것 같습니다.
혹시 틀린부분을 발견하시면 알려주시면 감사하겠습니다.