I have included a python solution which takes the prepossessed data (the list of length of all repeating elements, e.g., for 1,1,1,1,1,2,2,2,3,3 you should have a list [5,3,2] as input) .
The function comp(m,k) compute the f(m,k) in the solution.
For each repeating part, we compute how much we can save from dividing it into one more piece, and use maxheap on [Save, Length, Pieces, Current\ Cost, Next\ Cost] to perform the greedy algorithm. Each step, we pop the element that can save us most and update it.
def hfindb(a,k):
#
aa=[[comp(val,1)-comp(val,0),val,0,comp(val,0),comp(val,1)] for idx, val in enumerate(a)]
heapq.heapify(aa)
for i in range(k):
x=heapq.heappop(aa)
x[2]+=1
x[3]=x[4]
x[4]=comp(x[1],x[2]+1)
x[0]=x[4]-x[3]
heapq.heappush(aa,x)
return sum([x[3] for x in aa])
"For me, 1661F on paper was more or less 5 mins solve because I have already analyzed the cost function in MINMAXEQ"… aryanc403 _/_.
Upsolving is always important and everyone knows that? But when the sub problem is this much complex some people need some guidance who can’t solve this within 5 minutes, because not all are red at codeforces.