Array Splitting

2000ms

262144K

Description:

You are given an array $$$a_1, a_2, \dots, a_n$$$ and an integer $$$k$$$.

You are asked to divide this array into $$$k$$$ non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray. Let $$$f(i)$$$ be the index of subarray the $$$i$$$-th element belongs to. Subarrays are numbered from left to right and from $$$1$$$ to $$$k$$$.

Let the cost of division be equal to $$$\sum\limits_{i=1}^{n} (a_i \cdot f(i))$$$. For example, if $$$a = [1, -2, -3, 4, -5, 6, -7]$$$ and we divide it into $$$3$$$ subbarays in the following way: $$$[1, -2, -3], [4, -5], [6, -7]$$$, then the cost of division is equal to $$$1 \cdot 1 - 2 \cdot 1 - 3 \cdot 1 + 4 \cdot 2 - 5 \cdot 2 + 6 \cdot 3 - 7 \cdot 3 = -9$$$.

Calculate the maximum cost you can obtain by dividing the array $$$a$$$ into $$$k$$$ non-empty consecutive subarrays.

Input:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$ |a_i| \le 10^6$$$).

Output:

Print the maximum cost you can obtain by dividing the array $$$a$$$ into $$$k$$$ nonempty consecutive subarrays.

Sample Input:

5 2
-1 -2 5 -4 8

Sample Output:

Sample Input:

7 6
-3 0 -1 -2 -2 -4 -1

Sample Output:

-45

Sample Input:

4 1
3 -1 6 0

Sample Output:

Informação

Provedor Codeforces

Código CF1175D