{"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 such a way that the value of is maximized. Chosen sequence can be empty.\n\nPrint the maximum possible value of .\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 35, 1 ≤ _m_ ≤ 109).\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109).\n\n## Output\n\nPrint the maximum possible value of .\n\n[samples]\n\n## Note\n\nIn 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).\n\nIn the second example you can choose a sequence _b_ = {3}.","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_span[m]（#cf_span[1 ≤ n ≤ 35]，#cf_span[1 ≤ m ≤ 109]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]）。\n\n请输出可能的最大值。\n\n在第一个例子中，你可以选择序列 #cf_span[b = {1, 2}]，此时交错和等于 #cf_span[7]（取模 #cf_span[4] 后为 #cf_span[3]）。\n\n在第二个例子中，你可以选择序列 #cf_span[b = {3}]。\n\n## Input\n\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]）。\n\n## Output\n\n请输出可能的最大值。\n\n[samples]\n\n## Note\n\n在第一个例子中，你可以选择序列 #cf_span[b = {1, 2}]，此时交错和等于 #cf_span[7]（取模 #cf_span[4] 后为 #cf_span[3]）。在第二个例子中，你可以选择序列 #cf_span[b = {3}]。","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 < \\dots < b_k \\leq n $, where $ k \\geq 0 $ (empty sequence allowed).\n\nDefine the value of a sequence $ b $ as:\n$$\nS(b) = \\left( \\sum_{i=1}^{k} a_{b_i} \\right) \\bmod m\n$$\n\nObjective:\nMaximize $ S(b) $ over all possible subsequences $ b $ of $ \\{1, 2, \\dots, n\\} $.\n\nFind:\n$$\n\\max_{b \\subseteq \\{1,2,\\dots,n\\}} \\left( \\left( \\sum_{i \\in b} a_i \\right) \\bmod m \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF888E","tags":["bitmasks","divide and conquer","meet-in-the-middle"],"sample_group":[["4 4\n5 2 4 1","3"],["3 20\n199 41 299","19"]],"created_at":"2026-03-03 11:00:39"}}