Sum of weights - MarisaOJ: Marisa Online Judge

Given an array

$A$ of

$n$ integers, the weight of a consecutive subarray is defined as the sum of the

$k$ largest elements in the subarray, or the sum of all elements if the subarray has fewer than

$k$ elements. Compute the total weight of all consecutive subarrays of

$A$ . ### Input - The first line contains two integers

$n$ and

$k$ . - The second line contains

$n$ integers

$A_i$ . ### Output - Print a single integer representing the total weight of all subarrays, modulo

$10^9+7$ . ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le k \le 100$ . -

$1 \le A_i \le 10^9$ . ### Example

$6 3 3 1 5 3 2 6$

Output:

$164$

Topic

Others

Rating

2000

Solution (0)

Solution