Man, it isScout, TF2unfairhow good I am!

man, usaco is this week

i hope i get to plat

anyways, this problem!

it's absolute cancer, and the crap editorials i've found don't help either

so i'm writing this to help others suffer less

too lazy to describe the problem, just read the actual thing lol

but the dp relation is seemingly obvious, right?

just a lil

and then we're done, right?

right?

well the thing is, since all the elements depend on each other for the sum, we can't just consider each element independently and go from there

the key is in this expression for the example input given at the bottom of the statement: \[ |a_2-a_1|+|a_2-a_3|+|a_4-a_1|+|a_4-a_3|=1+2+2+1=6 \]

if we sort the example array to be `[1, 2, 3, 4]` (reorganizing the indices as needed),
note that the expression becomes:
\[ (a_4-a_3)+(a_3-a_1)+(a_4-a_2)+(a_3-a_2)=2a_4+a_3-2a_2-a_1 \]
i feel like just evaluating this expression is much easier than just having some arbitrary
definition of *unfairness*, no?

so instead of directly considering the minimum unfairness, let's just add how much each index contributes to that expression- that should be much easier than actually knowing what numbers we have to get the distance to or whatever crap

ok so let's do two things:

- sort our array so we don't have to worry about abs values (will explain later)
- redefine our dp as something actually calculable:

now, when we actually fill out our array and we're at `i` and `t`, we have two choices:

in this case, we know that we're going to add `i - t` and subtract
`(size - i) - (take_num - t)` of the current value

the first is because there's `i - t` non-selected elements in the left part of the array,
and we know the current element is bigger than the entire left half so

the second part is similar, it's because that's how many elements won't be selected in the later half

analogous to the first part

we add `t` and subtract `take_num - t` of the current element

that's because there's `t` selected elements to the left and `take_num - t` elements to the right

alright, we're done! the code naturally follows:

```py size, take_num = [int(i) for i in input().split()] arr = sorted(int(i) for i in input().split()) best_unfairness = [[float('inf')] * (take_num + 1) for _ in range(size + 1)] # set our base case best_unfairness[0][0] = 0 for i in range(1, size + 1): n = arr[i - 1] # just a shorthand # we can only take at most i elements, so yeah for t in range(min(i, take_num) + 1): # case 1: we include the number in our set include = float('inf') if t > 0: include = ( best_unfairness[i - 1][t - 1] + n * (i - t) - n * ((size - i) - (take_num - t)) ) # case 2: we just don't dont = float('inf') if best_unfairness[i - 1][t] != float('inf'): dont = ( best_unfairness[i - 1][t] + n * t - n * (take_num - t) ) best_unfairness[i][t] = min(include, dont) print(best_unfairness[size][take_num]) ```