问题2136--最大加密和(encryption)

2136: 最大加密和(encryption)

时间限制: 2 Sec  内存限制: 128 MB
提交: 6  解决: 5
[提交] [状态] [讨论版] [命题人:]

题目描述

csy给出了一个整数序列A,包含n个元素{a1, a2, …, an}。现在, csy要将这个n个元素拆分成k部分,要求如下:

1. 每个部分至少包含1个元素,并且每个部分由连续的元素构成

2. 没有两个部分重叠

3. 每部分和S需要取模p

csy希望每部分和的总和SUM最大化,问怎样拆分,可以让SUM最大,输出最大SUM。

例如n=4, k=3, p=10, A={3, 4, 7, 2}

将A分成{3, 4}, {7}, {2},得到的总和SUM=(3+4) mod p + 7 mod p + 2 mod p=16,是最大总和。

而例如 n=10, k=5, p=12, A={16, 3, 24, 13, 9, 8, 7, 5, 12, 12}

将A分成{16, 3, 24}, {13, 9}, {8}, {7}, {5, 12, 12}获得最大SUM=37

输入

第一行输入n, k, p

第二行输入n个整数ai

输出

输出最大SUM

样例输入 Copy

10 5 12
16 3 24 13 9 8 7 5 12 12

样例输出 Copy

37

提示

30%数据   k<=n<=100

60%数据   k<=n<=2000

100%数据  k<=n<=20000  2<=k<=50,  2<=p<=100  1<=ai<=10^6