C1. Encryption (easy)

Codeforces

IDCF958C1

Time1000ms

Memory256MB

Difficulty—

brute force

English · Original

Chinese · Translation

Formal · Original

Rebel spy Heidi has just obtained the plans for the Death Star from the Empire and, now on her way to safety, she is trying to break the encryption of the plans (of course they are encrypted – the Empire may be evil, but it is not stupid!). The encryption has several levels of security, and here is how the first one looks. Heidi is presented with a screen that shows her a sequence of integers _A_ and a positive integer _p_. She knows that the encryption code is a single number _S_, which is defined as follows: Define the score of _X_ to be the sum of the elements of _X_ modulo _p_. Heidi is given a sequence _A_ that consists of _N_ integers, and also given an integer _p_. She needs to split _A_ into 2 parts such that: * Each part contains at least 1 element of _A_, and each part consists of contiguous elements of _A_. * The two parts do not overlap. * The total sum _S_ of the scores of those two parts is maximized. This is the encryption code. Output the sum _S_, which is the encryption code. ## Input The first line of the input contains two space-separated integer _N_ and _p_ (2 ≤ _N_ ≤ 100 000, 2 ≤ _p_ ≤ 10 000) – the number of elements in _A_, and the modulo for computing scores, respectively. The second line contains _N_ space-separated integers which are the elements of _A_. Each integer is from the interval \[1, 1 000 000\]. ## Output Output the number _S_ as described in the problem statement. [samples] ## Note In the first example, the score is maximized if the input sequence is split into two parts as (3, 4), (7, 2). It gives the total score of . In the second example, the score is maximized if the first part consists of the first three elements, and the second part consists of the rest. Then, the score is .

叛徒间谍海蒂刚刚从帝国获得了死星的计划，现在她正前往安全地点，试图破解这些计划的加密（当然，它们是加密的——帝国可能邪恶，但并不愚蠢！）。加密有多层安全机制，而第一层如下所示。海蒂面前的屏幕上显示了一个整数序列 #cf_span[A] 和一个正整数 #cf_span[p]。她知道加密代码是一个单一的数字 #cf_span[S]，其定义如下：定义 #cf_span[X] 的 #cf_span(class=[tex-font-style-underline], body=[score]) 为 #cf_span[X] 中所有元素之和对 #cf_span[p] 取模的结果。海蒂被给定一个包含 #cf_span[N] 个整数的序列 #cf_span[A]，以及一个整数 #cf_span[p]。她需要将 #cf_span[A] 分成 #cf_span[2] 个部分，使得：请输出加密代码 #cf_span[S]。输入的第一行包含两个用空格分隔的整数 #cf_span[N] 和 #cf_span[p]（#cf_span[2 ≤ N ≤ 100 000]，#cf_span[2 ≤ p ≤ 10 000]）——分别是序列 #cf_span[A] 中的元素个数和计算得分时使用的模数。第二行包含 #cf_span[N] 个用空格分隔的整数，即序列 #cf_span[A] 的元素。每个整数均在区间 #cf_span[[1, 1 000 000]] 内。请输出如题所述的数字 #cf_span[S]。在第一个示例中，若将输入序列分为两部分 #cf_span[(3, 4)] 和 #cf_span[(7, 2)]，则得分最大。此时总得分为。在第二个示例中，若第一部分包含前三个元素，第二部分包含其余元素，则得分最大。此时得分为。 ## Input 输入的第一行包含两个用空格分隔的整数 #cf_span[N] 和 #cf_span[p]（#cf_span[2 ≤ N ≤ 100 000]，#cf_span[2 ≤ p ≤ 10 000]）——分别是序列 #cf_span[A] 中的元素个数和计算得分时使用的模数。第二行包含 #cf_span[N] 个用空格分隔的整数，即序列 #cf_span[A] 的元素。每个整数均在区间 #cf_span[[1, 1 000 000]] 内。 ## Output 请输出如题所述的数字 #cf_span[S]。 [samples] ## Note 在第一个示例中，若将输入序列分为两部分 #cf_span[(3, 4)] 和 #cf_span[(7, 2)]，则得分最大。此时总得分为。在第二个示例中，若第一部分包含前三个元素，第二部分包含其余元素，则得分最大。此时得分为。

**Definitions** Let $ N, p \in \mathbb{Z}^+ $ with $ 2 \leq N \leq 100{,}000 $ and $ 2 \leq p \leq 10{,}000 $. Let $ A = (a_1, a_2, \dots, a_N) $ be a sequence of integers with $ a_i \in [1, 1{,}000{,}000] $ for all $ i $. Define the *score* of a nonempty subsequence $ X \subseteq A $ (contiguous and ordered) as: $$ \text{score}(X) = \left( \sum_{x \in X} x \right) \bmod p $$ **Constraints** The sequence $ A $ must be partitioned into exactly two contiguous, nonempty subsequences: - First part: $ A_{1:i} = (a_1, a_2, \dots, a_i) $ for some $ i \in \{1, 2, \dots, N-1\} $ - Second part: $ A_{i+1:N} = (a_{i+1}, a_{i+2}, \dots, a_N) $ **Objective** Compute the maximum possible total score: $$ S = \max_{i \in \{1, \dots, N-1\}} \left( \text{score}(A_{1:i}) + \text{score}(A_{i+1:N}) \right) $$

Samples

Input #1

4 10
3 4 7 2

Output #1

Input #2

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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C1. Encryption (easy)",
    "description": {
      "content": "Rebel spy Heidi has just obtained the plans for the Death Star from the Empire and, now on her way to safety, she is trying to break the encryption of the plans (of course they are encrypted – the Emp",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF958C1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Rebel spy Heidi has just obtained the plans for the Death Star from the Empire and, now on her way to safety, she is trying to break the encryption of the plans (of course they are encrypted – the Emp...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "叛徒间谍海蒂刚刚从帝国获得了死星的计划，现在她正前往安全地点，试图破解这些计划的加密（当然，它们是加密的——帝国可能邪恶，但并不愚蠢！）。加密有多层安全机制，而第一层如下所示。\n\n海蒂面前的屏幕上显示了一个整数序列 #cf_span[A] 和一个正整数 #cf_span[p]。她知道加密代码是一个单一的数字 #cf_span[S]，其定义如下：\n\n定义 #cf_span[X] 的 #cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, p \\in \\mathbb{Z}^+ $ with $ 2 \\leq N \\leq 100{,}000 $ and $ 2 \\leq p \\leq 10{,}000 $.  \nLet $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of integers with $ a_i \\in [1, 1{,}0...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments