E. Maximum Subsequence

Codeforces

IDCF888E

Time1000ms

Memory256MB

Difficulty—

bitmasksdivide and conquermeet-in-the-middle

English · Original

Chinese · Translation

Formal · Original

You are given an array _a_ consisting of _n_ integers, and additionally an integer _m_. You have to choose some sequence of indices _b_1, _b_2, ..., _b__k_ (1 ≤ _b_1 < _b_2 < ... < _b__k_ ≤ _n_) in such a way that the value of is maximized. Chosen sequence can be empty. Print the maximum possible value of . ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 35, 1 ≤ _m_ ≤ 109). The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109). ## Output Print the maximum possible value of . [samples] ## Note In the first example you can choose a sequence _b_ = {1, 2}, so the sum is equal to 7 (and that's 3 after taking it modulo 4). In the second example you can choose a sequence _b_ = {3}.

你被给定一个包含 #cf_span[n] 个整数的数组 #cf_span[a]，以及一个整数 #cf_span[m]。你需要选择一个下标序列 #cf_span[b1, b2, ..., bk]（#cf_span[1 ≤ b1 < b2 < ... < bk ≤ n]），使得交错和的值最大化。所选序列可以为空。请输出可能的最大值。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 35]，#cf_span[1 ≤ m ≤ 109]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]）。请输出可能的最大值。在第一个例子中，你可以选择序列 #cf_span[b = {1, 2}]，此时交错和等于 #cf_span[7]（取模 #cf_span[4] 后为 #cf_span[3]）。在第二个例子中，你可以选择序列 #cf_span[b = {3}]。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 35]，#cf_span[1 ≤ m ≤ 109]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]）。 ## Output 请输出可能的最大值。 [samples] ## Note 在第一个例子中，你可以选择序列 #cf_span[b = {1, 2}]，此时交错和等于 #cf_span[7]（取模 #cf_span[4] 后为 #cf_span[3]）。在第二个例子中，你可以选择序列 #cf_span[b = {3}]。

Given: - An integer $ n $, an integer $ m $, and an array $ a = [a_1, a_2, \dots, a_n] $ of $ n $ positive integers. - A sequence of indices $ b = (b_1, b_2, \dots, b_k) $ such that $ 1 \leq b_1 < b_2 < \dots < b_k \leq n $, where $ k \geq 0 $ (empty sequence allowed). Define the value of a sequence $ b $ as: $$ S(b) = \left( \sum_{i=1}^{k} a_{b_i} \right) \bmod m $$ Objective: Maximize $ S(b) $ over all possible subsequences $ b $ of $ \{1, 2, \dots, n\} $. Find: $$ \max_{b \subseteq \{1,2,\dots,n\}} \left( \left( \sum_{i \in b} a_i \right) \bmod m \right) $$

Samples

Input #1

4 4
5 2 4 1

Output #1

Input #2

3 20
199 41 299

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Maximum Subsequence",
    "description": {
      "content": "You are given an array _a_ consisting of _n_ integers, and additionally an integer _m_. You have to choose some sequence of indices _b_1, _b_2, ..., _b__k_ (1 ≤ _b_1 < _b_2 < ... < _b__k_ ≤ _n_) in su",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF888E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array _a_ consisting of _n_ integers, and additionally an integer _m_. You have to choose some sequence of indices _b_1, _b_2, ..., _b__k_ (1 ≤ _b_1 < _b_2 < ... < _b__k_ ≤ _n_) in su...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个包含 #cf_span[n] 个整数的数组 #cf_span[a]，以及一个整数 #cf_span[m]。你需要选择一个下标序列 #cf_span[b1, b2, ..., bk]（#cf_span[1 ≤ b1 < b2 < ... < bk ≤ n]），使得交错和的值最大化。所选序列可以为空。\n\n请输出可能的最大值。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given:\n- An integer $ n $, an integer $ m $, and an array $ a = [a_1, a_2, \\dots, a_n] $ of $ n $ positive integers.\n- A sequence of indices $ b = (b_1, b_2, \\dots, b_k) $ such that $ 1 \\leq b_1 < b_2...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments