This problem is given in SRM 536 Div 2 for 1000 points. The problem is that we are given revenues of n companies and we need to merge all the companies to one company. If we merge company i to j then the revenue of merged company is the average of the revenue generated by company i to j. We must merge atleast k companies.

Link for the editorial of the problem: https://web.archive.org/web/20120421042646/http://apps.topcoder.com/wiki/display/tc/SRM+536

Now my doubt in the editorial is where it says that: best[i] can either be

• (revenue[0] + ... + revenue[i-1])/i or

• (best[j] + revenues[j] + revenues[j + 1] + ... + revenues[i-1]) / (i-j + 1) for some j between k and i-1, inclusive.

In the second point, for a given i and k, let's take j = i-1. Then the expression would be (best[i-1]+revenue[i-1])/2. best[i-1] is the best revenue that can be generated from 0 to i-2 companies. Hence in this state, we are merging all the companies from 0 to i-2 and then we merge that resultant company with (i-1)th company. But isn't the last step illegal if we have k>2?? Is there a problem with my understanding of solution??