CF958C2 Encryption (medium)

Heidi 现在已经破解了死星计划的第一层加密，并正盯着屏幕，上面显示着她需要输入的下一个代码的描述。它看起来和第一个非常相似——看来帝国的工程师们相当懒惰…… Heidi 再次得到了一个序列 $A$，但这次她还得到了两个整数 $k$ 和 $p$。她需要找出加密密钥 $S$。 设 $X$ 是一个整数序列，$p$ 是一个正整数。我们定义 $X$ 的得分为 $X$ 所有元素之和对 $p$ 取模的结果。 Heidi 得到了一个包含 $N$ 个整数的序列 $A$，还得到了整数 $k$ 和 $p$。她的目标是将 $A$ 分成 $k$ 段，使得： - 每一段至少包含 $A$ 的 $1$ 个元素，并且每一段由 $A$ 的连续元素组成。 - 各段之间没有重叠。 - 这些段的得分之和 $S$ 最大。 请输出 $S$——即加密代码。

输入的第一行包含三个用空格分隔的整数 $N$、$k$ 和 $p$（$k \leq N \leq 20000$，$2 \leq k \leq 50$，$2 \leq p \leq 100$）——表示 $A$ 的元素个数、需要分成的段数以及计算得分时的模数。 第二行包含 $N$ 个用空格分隔的整数，表示序列 $A$ 的元素。每个整数都在区间 $[1,1000000]$ 内。

输出题目描述中所要求的 $S$。

在第一个样例中，如果将输入序列分为 $(3,4)$、$(7)$、$(2)$，总得分为 $((3+4) \bmod 10) + (7 \bmod 10) + (2 \bmod 10) = 7 + 7 + 2 = 16$。很容易看出这个得分是最大的。 在第二个样例中，一种得到得分 $37$ 的分法是：$(16,3,24)$、$(13,9)$、$(8)$、$(7)$、$(5,12,12)$。 由 ChatGPT 4.1 翻译。