1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <limits.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(a,b) {uint64_t t = (a); (a) = (b); (b) = t;}
int cmp(const void *a, const void *b){
return *(uint64_t*)b - *(uint64_t*)a;
}
int n, k;
uint64_t nums[25];
uint64_t sets[25][25];
uint64_t sums[25] = {0};
uint64_t sq_sums[25] = {0};
int len[25] = {0};
uint64_t min_sum = ULLONG_MAX;
uint64_t get_sum(uint64_t sets[25][25], int len[25]){
uint64_t ans = 0;
for(int i = 0; i < k; i++){
uint64_t s = 0;
for(int j = 0; j < len[i]; j++) s += sets[i][j];
ans += (s * s);
}
return ans;
}
void dfs(int nums_idx, uint64_t sets[25][25], int len[25], uint64_t sums[25], uint64_t now_sq_sum){
if(now_sq_sum >= min_sum) return;
if(nums_idx == n){
min_sum = min(min_sum, now_sq_sum);
return;
}
else {
for(int i = 0; i < k; i++){
int flag = 1;
if(len[i] == 0) flag = 0;
sets[i][len[i]] = nums[nums_idx];
uint64_t temp = now_sq_sum - (sums[i] * sums[i]);
sums[i] += nums[nums_idx], len[i]++;
dfs(nums_idx + 1, sets, len, sums, temp + (sums[i] * sums[i]));
sums[i] -= nums[nums_idx], len[i]--;
if(!flag) return;
}
}
}
int main(){
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++) scanf("%llu", &nums[i]);
qsort(nums, n, sizeof(uint64_t), cmp);
dfs(0, sets, len, sums, 0);
printf("%llu\n", min_sum);
}
|