English · Original
Chinese · Translation
Formal · Original
_Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount._
You are given an array _a_ of length _n_ and an integer _c_.
The value of some array _b_ of length _k_ is the sum of its elements except for the smallest. For example, the value of the array \[3, 1, 6, 5, 2\] with _c_ = 2 is 3 + 6 + 5 = 14.
Among all possible partitions of _a_ into contiguous subarrays output the smallest possible sum of the values of these subarrays.
## Input
The first line contains integers _n_ and _c_ (1 ≤ _n_, _c_ ≤ 100 000).
The second line contains _n_ integers _a__i_ (1 ≤ _a__i_ ≤ 109) — elements of _a_.
## Output
Output a single integer — the smallest possible sum of values of these subarrays of some partition of _a_.
[samples]
## Note
In the first example any partition yields 6 as the sum.
In the second example one of the optimal partitions is \[1, 1\], \[10, 10, 10, 10, 10, 10, 9, 10, 10, 10\] with the values 2 and 90 respectively.
In the third example one of the optimal partitions is \[2, 3\], \[6, 4, 5, 7\], \[1\] with the values 3, 13 and 1 respectively.
In the fourth example one of the optimal partitions is \[1\], \[3, 4, 5, 5, 3, 4\], \[1\] with the values 1, 21 and 1 respectively.
_由于你是最强大的幽灵之王，位于文尼察市中心的 Nizhniy Magazin «Mir» 正为你提供折扣。_
给定一个长度为 #cf_span[n] 的数组 #cf_span[a] 和一个整数 #cf_span[c]。
某个长度为 #cf_span[k] 的数组 #cf_span[b] 的值定义为：其所有元素之和减去最小的元素。例如，数组 #cf_span[[3, 1, 6, 5, 2]] 在 #cf_span[c = 2] 时的值为 #cf_span[3 + 6 + 5 = 14]。
在所有可能的将 #cf_span[a] 划分为连续子数组的方案中，请输出这些子数组的值之和的最小可能值。
第一行包含两个整数 #cf_span[n] 和 #cf_span[c]（#cf_span[1 ≤ n, c ≤ 100 000]）。
第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 10^9]）——数组 #cf_span[a] 的元素。
请输出一个整数——某个对 #cf_span[a] 的划分中，这些子数组的值之和的最小可能值。
在第一个示例中，任何划分的和均为 6。
在第二个示例中，一种最优划分是 #cf_span[[1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10]]，其值分别为 2 和 90。
在第三个示例中，一种最优划分是 #cf_span[[2, 3], [6, 4, 5, 7], [1]]，其值分别为 3、13 和 1。
在第四个示例中，一种最优划分是 #cf_span[[1], [3, 4, 5, 5, 3, 4], [1]]，其值分别为 1、21 和 1。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[c]（#cf_span[1 ≤ n, c ≤ 100 000]）。第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 10^9]）——数组 #cf_span[a] 的元素。
## Output
请输出一个整数——某个对 #cf_span[a] 的划分中，这些子数组的值之和的最小可能值。
[samples]
## Note
在第一个示例中，任何划分的和均为 6。在第二个示例中，一种最优划分是 #cf_span[[1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10]]，其值分别为 2 和 90。在第三个示例中，一种最优划分是 #cf_span[[2, 3], [6, 4, 5, 7], [1]]，其值分别为 3、13 和 1。在第四个示例中，一种最优划分是 #cf_span[[1], [3, 4, 5, 5, 3, 4], [1]]，其值分别为 1、21 和 1。
**Definitions**
Let $ n, c \in \mathbb{Z}^+ $ with $ 1 \leq n, c \leq 100{,}000 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ 1 \leq a_i \leq 10^9 $.
For any non-empty subarray $ B = (b_1, b_2, \dots, b_k) $, define its *value* as:
$$
\text{value}(B) = \sum_{i=1}^k b_i - \min(B)
$$
if $ k \geq c $, and $ \text{value}(B) = \sum_{i=1}^k b_i $ if $ k < c $.
**Constraints**
1. $ 1 \leq n \leq 100{,}000 $
2. $ 1 \leq c \leq 100{,}000 $
3. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Partition $ A $ into $ m $ contiguous non-empty subarrays $ B_1, B_2, \dots, B_m $ such that the total sum
$$
\sum_{j=1}^m \text{value}(B_j)
$$
is minimized. Output this minimum total sum.
API Response (JSON)
{
"problem": {
"name": "E. Cashback",
"description": {
"content": "_Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount._ You are given an array _a_ of length _n_ and an integer _c_. The value of some arra",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF940E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount._\n\nYou are given an array _a_ of length _n_ and an integer _c_.\n\nThe value of some arra...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_由于你是最强大的幽灵之王，位于文尼察市中心的 Nizhniy Magazin «Mir» 正为你提供折扣。_ \n\n给定一个长度为 #cf_span[n] 的数组 #cf_span[a] 和一个整数 #cf_span[c]。 \n\n某个长度为 #cf_span[k] 的数组 #cf_span[b] 的值定义为：其所有元素之和减去最小的元素。例如，数组 #cf_span[[3, 1, 6, 5, 2]...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, c \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, c \\leq 100{,}000 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 1 \\leq a_i \\leq 10^9 $. \n\nFor any non-empty ...",
"is_translate": false,
"language": "Formal"
}
]
}