English · Original
Chinese · Translation
Formal · Original
Princess Heidi decided to give orders to all her _K_ Rebel ship commanders in person. Unfortunately, she is currently travelling through hyperspace, and will leave it only at _N_ specific moments _t_1, _t_2, ..., _t__N_. The meetings with commanders must therefore start and stop at those times. Namely, each commander will board her ship at some time _t__i_ and disembark at some later time _t__j_. Of course, Heidi needs to meet with all commanders, and no two meetings can be held during the same time. Two commanders cannot even meet at the beginnings/endings of the hyperspace jumps, because too many ships in one position could give out their coordinates to the enemy.
Your task is to find minimum time that Princess Heidi has to spend on meetings, with her schedule satisfying the conditions above.
## Input
The first line contains two integers _K_, _N_ (2 ≤ 2_K_ ≤ _N_ ≤ 500000, _K_ ≤ 5000). The second line contains _N_ distinct integers _t_1, _t_2, ..., _t__N_ (1 ≤ _t__i_ ≤ 109) representing the times when Heidi leaves hyperspace.
## Output
Output only one integer: the minimum time spent on meetings.
[samples]
## Note
In the first example, there are five valid schedules: \[1, 4\], \[6, 7\] with total time 4, \[1, 4\], \[6, 12\] with total time 9, \[1, 4\], \[7, 12\] with total time 8, \[1, 6\], \[7, 12\] with total time 10, and \[4, 6\], \[7, 12\] with total time 7. So the answer is 4.
In the second example, there is only 1 valid schedule: \[1, 2\], \[3, 4\], \[5, 6\].
For the third example, one possible schedule with total time 6 is: \[1, 3\], \[4, 5\], \[14, 15\], \[23, 25\].
公主海蒂决定亲自向她的 #cf_span[K] 位叛军舰长下达命令。不幸的是，她目前正穿越超空间，仅会在 #cf_span[N] 个特定时刻 #cf_span[t1, t2, ..., tN] 离开超空间。因此，与舰长们的会面必须在这些时刻开始和结束。具体而言，每位舰长将在某个时刻 #cf_span[ti] 登舰，并在之后的某个时刻 #cf_span[tj] 离舰。当然，海蒂需要与所有舰长会面，且不能在相同时间举行两场会面。两个舰长甚至不能在超空间跳跃的开始/结束时刻相遇，因为过多的飞船聚集在同一位置可能向敌人暴露坐标。
你的任务是找到满足上述条件的、公主海蒂所花费的最少会面总时间。
第一行包含两个整数 #cf_span[K], #cf_span[N] (#cf_span[2 ≤ 2K ≤ N ≤ 500000], #cf_span[K ≤ 5000])。第二行包含 #cf_span[N] 个互不相同的整数 #cf_span[t1, t2, ..., tN] (#cf_span[1 ≤ ti ≤ 109])，表示海蒂离开超空间的时刻。
仅输出一个整数：会面所花费的最少时间。
在第一个例子中，有五种有效安排：#cf_span[[1, 4], [6, 7]] 总时间为 4，#cf_span[[1, 4], [6, 12]] 总时间为 9，#cf_span[[1, 4], [7, 12]] 总时间为 8，#cf_span[[1, 6], [7, 12]] 总时间为 10，以及 #cf_span[[4, 6], [7, 12]] 总时间为 7。因此答案为 4。
在第二个例子中，仅有一种有效安排：#cf_span[[1, 2], [3, 4], [5, 6]]。
对于第三个例子，一种总时间为 6 的可能安排是：#cf_span[[1, 3], [4, 5], [14, 15], [23, 25]]。
## Input
第一行包含两个整数 #cf_span[K], #cf_span[N] (#cf_span[2 ≤ 2K ≤ N ≤ 500000], #cf_span[K ≤ 5000])。第二行包含 #cf_span[N] 个互不相同的整数 #cf_span[t1, t2, ..., tN] (#cf_span[1 ≤ ti ≤ 109])，表示海蒂离开超空间的时刻。
## Output
仅输出一个整数：会面所花费的最少时间。
[samples]
## Note
在第一个例子中，有五种有效安排：#cf_span[[1, 4], [6, 7]] 总时间为 4，#cf_span[[1, 4], [6, 12]] 总时间为 9，#cf_span[[1, 4], [7, 12]] 总时间为 8，#cf_span[[1, 6], [7, 12]] 总时间为 10，以及 #cf_span[[4, 6], [7, 12]] 总时间为 7。因此答案为 4。在第二个例子中，仅有一种有效安排：#cf_span[[1, 2], [3, 4], [5, 6]]。对于第三个例子，一种总时间为 6 的可能安排是：#cf_span[[1, 3], [4, 5], [14, 15], [23, 25]]。
**Definitions**
Let $ K \in \mathbb{Z}^+ $ be the number of commanders.
Let $ N \in \mathbb{Z}^+ $ be the number of hyperspace exit times, with $ 2 \leq 2K \leq N \leq 500000 $ and $ K \leq 5000 $.
Let $ T = (t_1, t_2, \dots, t_N) $ be a strictly increasing sequence of distinct real numbers representing the times when Heidi exits hyperspace: $ t_1 < t_2 < \dots < t_N $.
Each meeting is an interval $ [t_i, t_j] $ with $ i < j $, representing a commander boarding at $ t_i $ and disembarking at $ t_j $.
Meetings must be non-overlapping: no two intervals may share any endpoint or interior point.
Each meeting corresponds to a unique pair $ (i, j) $, and exactly $ K $ such intervals must be selected.
**Constraints**
1. Exactly $ K $ disjoint intervals $ [t_{i_k}, t_{j_k}] $ are chosen, with $ i_k < j_k $ for all $ k \in \{1, \dots, K\} $.
2. All endpoints $ t_{i_k}, t_{j_k} $ are distinct elements of $ T $.
3. Intervals are non-overlapping: for any two intervals $ [t_a, t_b] $ and $ [t_c, t_d] $, either $ t_b \leq t_c $ or $ t_d \leq t_a $.
**Objective**
Minimize the total duration of the $ K $ meetings:
$$
\min \sum_{k=1}^{K} (t_{j_k} - t_{i_k})
$$
subject to the above constraints.
API Response (JSON)
{
"problem": {
"name": "E2. Guard Duty (medium)",
"description": {
"content": "Princess Heidi decided to give orders to all her _K_ Rebel ship commanders in person. Unfortunately, she is currently travelling through hyperspace, and will leave it only at _N_ specific moments _t_1",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF958E2"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Princess Heidi decided to give orders to all her _K_ Rebel ship commanders in person. Unfortunately, she is currently travelling through hyperspace, and will leave it only at _N_ specific moments _t_1...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "公主海蒂决定亲自向她的 #cf_span[K] 位叛军舰长下达命令。不幸的是，她目前正穿越超空间，仅会在 #cf_span[N] 个特定时刻 #cf_span[t1, t2, ..., tN] 离开超空间。因此，与舰长们的会面必须在这些时刻开始和结束。具体而言，每位舰长将在某个时刻 #cf_span[ti] 登舰，并在之后的某个时刻 #cf_span[tj] 离舰。当然，海蒂需要与所有舰长会面，且...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ K \\in \\mathbb{Z}^+ $ be the number of commanders. \nLet $ N \\in \\mathbb{Z}^+ $ be the number of hyperspace exit times, with $ 2 \\leq 2K \\leq N \\leq 500000 $ and $ K \\leq 5000 $...",
"is_translate": false,
"language": "Formal"
}
]
}