18669번 - Yet Another Mex Problem 다국어

You are given an array a of length n and an integer k. You need to find the optimal way to divide the given array into several continuous subarrays with lengths no more than k, to maximize your profit. The profit for one subarray is the sum of its elements multiplied by the mex value of this subarray. You total profit is the sum of profits for all subarrays.

We define the value of mex of a set of non-negative integers as the smallest non-negative integer which doesn’t belong to this set. For example: mex (0, 1, 3) = 2.

The first line contains two integers: n (2 ≤ n ≤ 200 000), the length of the array, and k (1 ≤ k ≤ n), upper bound for the subarray length.

The second line contains n integers, the elements of the array: the i-th integer is a_i, 0 ≤ a_i ≤ n.

Print a single non-negative integer: the maximum possible profit that can be achieved by dividing the given array into subarrays with lengths no more than k.