{"problem":{"name":"C2. Encryption (medium)","description":{"content":"Heidi has now broken the first level of encryption of the Death Star plans, and is staring at the screen presenting her with the description of the next code she has to enter. It looks surprisingly si","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF958C2"},"statements":[{"statement_type":"Markdown","content":"Heidi has now broken the first level of encryption of the Death Star plans, and is staring at the screen presenting her with the description of the next code she has to enter. It looks surprisingly similar to the first one – seems like the Empire engineers were quite lazy...\n\nHeidi is once again given a sequence _A_, but now she is also given two integers _k_ and _p_. She needs to find out what the encryption key _S_ is.\n\nLet _X_ be a sequence of integers, and _p_ a positive integer. We define the score of _X_ to be the sum of the elements of _X_ modulo _p_.\n\nHeidi is given a sequence _A_ that consists of _N_ integers, and also given integers _k_ and _p_. Her goal is to split _A_ into _k_ part such that:\n\n*   Each part contains at least 1 element of _A_, and each part consists of contiguous elements of _A_.\n*   No two parts overlap.\n*   The total sum _S_ of the scores of those parts is maximized.\n\nOutput the sum _S_ – the encryption code.\n\n## Input\n\nThe first line of the input contains three space-separated integer _N_, _k_ and _p_ (_k_ ≤ _N_ ≤ 20 000, 2 ≤ _k_ ≤ 50, 2 ≤ _p_ ≤ 100) – the number of elements in _A_, the number of parts _A_ should be split into, and the modulo for computing scores, respectively.\n\nThe second line contains _N_ space-separated integers that are the elements of _A_. Each integer is from the interval \\[1, 1 000 000\\].\n\n## Output\n\nOutput the number _S_ as described in the problem statement.\n\n[samples]\n\n## Note\n\nIn the first example, if the input sequence is split as (3, 4), (7), (2), the total score would be . It is easy to see that this score is maximum.\n\nIn the second example, one possible way to obtain score 37 is to make the following split: (16, 3, 24), (13, 9), (8), (7), (5, 12, 12).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Heidi 已经破解了死星计划的第一层加密，现在她正面对屏幕，屏幕上显示着她需要输入的下一个密码的描述。这看起来与第一个密码惊人地相似——似乎帝国工程师们相当懒惰……\n\nHeidi 再次获得一个序列 $A$，但她还得到了两个整数 $k$ 和 $p$。她需要找出加密密钥 $S$。\n\n设 $X$ 为一个整数序列，$p$ 为一个正整数。我们定义 $X$ 的 $\\underline{score}$ 为 $X$ 中所有元素之和对 $p$ 取模的结果。\n\nHeidi 被给定一个包含 $N$ 个整数的序列 $A$，以及整数 $k$ 和 $p$。她的目标是将 $A$ 分成 $k$ 个部分，使得：\n\n输出总和 $S$ —— 加密密码。\n\n输入的第一行包含三个用空格分隔的整数 $N$、$k$ 和 $p$（$k ≤ N ≤ 20 000$，$2 ≤ k ≤ 50$，$2 ≤ p ≤ 100$）——分别表示序列 $A$ 的元素个数、$A$ 需要被分割成的部分数，以及计算得分时使用的模数。\n\n第二行包含 $N$ 个用空格分隔的整数，即序列 $A$ 的元素。每个整数均在区间 $[1, 1 000 000]$ 内。\n\n请输出如题所述的数字 $S$。\n\n在第一个示例中，若输入序列被分割为 $(3, 4)$、$(7)$、$(2)$，则总得分为 。可以轻易看出，该得分是最大的。\n\n在第二个示例中，一种获得得分 $37$ 的可能分割方式是：$(16, 3, 24)$、$(13, 9)$、$(8)$、$(7)$、$(5, 12, 12)$。\n\n## Input\n\n输入的第一行包含三个用空格分隔的整数 $N$、$k$ 和 $p$（$k ≤ N ≤ 20 000$，$2 ≤ k ≤ 50$，$2 ≤ p ≤ 100$）——分别表示序列 $A$ 的元素个数、$A$ 需要被分割成的部分数，以及计算得分时使用的模数。第二行包含 $N$ 个用空格分隔的整数，即序列 $A$ 的元素。每个整数均在区间 $[1, 1 000 000]$ 内。\n\n## Output\n\n请输出如题所述的数字 $S$。\n\n[samples]\n\n## Note\n\n在第一个示例中，若输入序列被分割为 $(3, 4)$、$(7)$、$(2)$，则总得分为 。可以轻易看出，该得分是最大的。在第二个示例中，一种获得得分 $37$ 的可能分割方式是：$(16, 3, 24)$、$(13, 9)$、$(8)$、$(7)$、$(5, 12, 12)$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, k, p \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of integers, where $ a_i \\in [1, 10^6] $.  \n\nA *partition* of $ A $ into $ k $ contiguous non-empty parts is a sequence of indices $ 0 = i_0 < i_1 < i_2 < \\dots < i_k = N $, defining $ k $ subsequences:  \n$ X_j = (a_{i_{j-1}+1}, a_{i_{j-1}+2}, \\dots, a_{i_j}) $ for $ j = 1, \\dots, k $.  \n\nDefine the *score* of a part $ X_j $ as:  \n$$\n\\text{score}(X_j) = \\left( \\sum_{x \\in X_j} x \\right) \\bmod p\n$$  \n\nDefine the *total score* $ S $ of a partition as:  \n$$\nS = \\sum_{j=1}^k \\text{score}(X_j)\n$$\n\n**Constraints**  \n1. $ k \\leq N \\leq 20000 $  \n2. $ 2 \\leq k \\leq 50 $  \n3. $ 2 \\leq p \\leq 100 $  \n4. $ 1 \\leq a_i \\leq 10^6 $ for all $ i \\in \\{1, \\dots, N\\} $\n\n**Objective**  \nMaximize the total score $ S $ over all possible ways to partition $ A $ into exactly $ k $ contiguous non-empty parts.  \nOutput the maximum possible value of $ S $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF958C2","tags":["dp"],"sample_group":[["4 3 10\n3 4 7 2","16"],["10 5 12\n16 3 24 13 9 8 7 5 12 12","37"]],"created_at":"2026-03-03 11:00:39"}}