I was asked this problem in Bytedance OA.
N points are given on a line and K special points can be setup anywhere. You have to find the sum of shortest distances for each point to any special point. I know a solution like grouping points, and then for each group, sum of distances to their median, but it didn't work that time. I am thinking some DP but unable to figure out.
Constraints are N, K <= 100
Coordinates of points 1 <= C[i] <= 10^4.
What is the problem with brute force $$$O(NK)$$$?
This is kind of some similar stuff.
Auto comment: topic has been updated by scar_face (previous revision, new revision, compare).
check this one
https://codeforces.net/contest/1283/problem/D