My solution is not completely correct, as I got 112 points out of 160 (it was a strong greedy that I did not prove and turned out as incorrect (or I just had a bug, idk)).

1) If we visualize the children as nodes in a graph, and there's an edge between every pair of (child, best friend), then because every node has exactly an indegree and outdegree of 1, this graph is just made of several components (can be 1 component) of simple cycles. So we can pick which values to give to every cycle.

2) Let's say we gave every cycle the values we want to give to its nodes. How do we distribute them optimally? Claim: We sort the values and we go by this pattern (I'll write the indicies of elements we take after we sort, and we'll assign them to the cycle one next to the other):

0 2 4 6 8 10 ........ 9 7 5 3 1. (note that because it is a cycle, the last value (at index 1 here) will be also connected to the first value (at index 0 here)).

Proof: Let's denote in the above array, D[i] = A[i] — A[i — 1]. Note that all D[i] are positive as we sorted the array. So, if we go by this pattern, the maximal difference between the pairs of adjacent nodes in the cycle is: max(D[1] + D[2], D[2] + D[3], D[3] + D[4], D[4] + D[5], .....).

It is basically the maximal sum of 2 adjacent values in the array D (you might want to draw the pattern on paper and see for yourself). Without loss of generality (and to make explanation simpler), let's suppose the maximal sum is, for instance, D[5] + D[6]. This is equal to (A[5] — A[4]) + (A[6] — A[5]) = A[6] — A[4].

We would want to get rid of this difference. In the pattern, let's split it to 2 halves: the increasing half, and the decreasing half (I'm sure you can understand what I'm saying here).

In both halves, in order to get rid of this difference we need to take the element A[5]. Why is that? Because if we don't take the element A[5] in, say, the first half, then we must have took 2 elements A[x] and A[y] right next to each other, so that (x <= 4, y >= 6): A[y] — A[x] >= A[6] — A[4] in that case.

However, we can't take the element A[5] in both halves, since we must take every element exactly once. So this proves the pattern is optimal. From now we'll consider the whole array A, from which we take elements, as sorted.

We will also precompute: ans[i][j] = this maximal sum for a subarray from index i to index j in the array A. We can easily compute it in O(n^3) with pure bruteforce, and also easily in O(n^2) but it doesn't matter really.

3) Now let's consider the cycles by just their sizes. So now we have a group of values that denote sizes, and their sum is N. We would like to give to every cycle some elements from the array A, the number of elements should be equal to its size.

Claim: For a size of cycle X, we want to pick from the array A a subarray (contiguous) of size X. I did not prove this claim though, it's very intuitive.

4) This is the greedy part: we need to decide for every size, the subarray we give to it. I tried to come up with some kind of DP, but failed (at least one that fits in the time limit). So I decided to do some binary search over the answer to the problem:

Note that: ans[i — 1][j] <= ans[i][j] <= ans[i][j + 1]. We will use this property. Let's say in the current binary search iteration we have our "mid". First off, we insert all sizes of cycles into some multimap (first is size, second is the index of the cycle so that we can reconstruct).

We start from index 0, and we binary search on the largest X such that ans[0][X] <= mid. Once we find this X, we find the largest size in the multimap that is at most the size of this subarray, and use this size S for the subarray ans[0][S-1] (if there is no such size in the multimap, then we say there's no answer with that mid). Then we remove this size from the multimap, set our start index from S, and repeat the process.