utils/scrapers/prescraped/codeforces/Problems/1942D

Pristine Beat - Touhou⠀Elsie is learning how to paint. She has a canvas of n cells numbered from 1 to n and can paint any (potentially empty) subset of cells.  Elsie has a 2D array a which she will use to evaluate paintings. Let the maximal contiguous intervals of painted cells in a painting be [l1,r1],[l2,r2],…,[lx,rx]. The beauty of the painting is the sum of ali,ri over all 1≤i≤x. In the image above, the maximal contiguous intervals of painted cells are [2,4],[6,6],[8,9] and the beauty of the painting is a2,4+a6,6+a8,9.There are 2n ways to paint the strip. Help Elsie find the k largest possible values of the beauty of a painting she can obtain, among all these ways. Note that these k values do not necessarily have to be distinct. It is guaranteed that there are at least k different ways to paint the canvas.