#P11702. [ROIR 2025] 不平衡划分

[ROIR 2025] 不平衡划分

题目背景

翻译自 ROIR 2025 D2T2

题目描述

给定一个非负整数数组 [a1,a2,,an][a_1, a_2, \dots, a_n]。考虑将该数组划分成 kk 个非空的连续子段。我们称划分方案的“不平衡度”为这些子段和中的最大值与最小值之差。你需要求出将该数组划分成 kk 个子段时的最大不平衡度。

例如,如果数组为 [2,1,3,4][2, 1, 3, 4]k=2k=2,则:

  • 划分为 [2,1,3][4][2, 1, 3][4] 时,不平衡度为 64=26 - 4 = 2
  • 划分为 [2,1][3,4][2, 1][3, 4] 时,不平衡度为 73=47 - 3 = 4
  • 划分为 [2][1,3,4][2][1, 3, 4] 时,不平衡度为 82=68 - 2 = 6

其中最后一种情况的不平衡度最大。

输入格式

第一行输入两个整数 nnkk2kn3000002 \le k \le n \le 300000),分别表示数组的长度和需要划分的子段的数量。

第二行包含 nn 个整数 a1,a2,,ana_1,a_2,\dots,a_n0ai1090 \le a_i \le 10^9)。

输出格式

输出一个整数,即将该数组划分为 kk 个子段时的最大不平衡度。

4 2
2 1 3 4
6

5 4
2 1 3 4 1
6

提示

在样例二中,最优划分方案是 [2][1][3,4][1][2][1][3, 4][1]。其中最大子段和为 3+4=73 + 4 = 7,最小子段和为 11,因此不平衡度为 71=67 - 1 = 6

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。

子任务 分数 特殊性质
11 1111 n15n \le 15
22 k=2k = 2
33 2121 k=3k = 3
44 1515 n300n \le 300
55 2121 n3000n \le 3000
66 21 21