{"problem":{"name":"C. Vladik and Memorable Trip","description":{"content":"Vladik often travels by trains. He remembered some of his trips especially well and I would like to tell you about one of these trips: Vladik is at initial train station, and now _n_ people (includin","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF811C"},"statements":[{"statement_type":"Markdown","content":"Vladik often travels by trains. He remembered some of his trips especially well and I would like to tell you about one of these trips:\n\nVladik is at initial train station, and now _n_ people (including Vladik) want to get on the train. They are already lined up in some order, and for each of them the city code _a__i_ is known (the code of the city in which they are going to).\n\nTrain chief selects some number of disjoint segments of the original sequence of people (covering entire sequence by segments is **not necessary**). People who are in the same segment will be in the same train carriage. The segments are selected in such way that if at least one person travels to the city _x_, then all people who are going to city _x_ should be in the same railway carriage. This means that they can’t belong to different segments. Note, that all people who travel to the city _x_, either go to it and in the same railway carriage, or do not go anywhere at all.\n\nComfort of a train trip with people on segment from position _l_ to position _r_ is equal to _XOR_ of all distinct codes of cities for people on the segment from position _l_ to position _r_. _XOR_ operation also known as exclusive _OR_.\n\nTotal comfort of a train trip is equal to sum of comfort for each segment.\n\nHelp Vladik to know maximal possible total comfort.\n\n## Input\n\nFirst line contains single integer _n_ (1 ≤ _n_ ≤ 5000) — number of people.\n\nSecond line contains _n_ space-separated integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 5000), where _a__i_ denotes code of the city to which _i_\\-th person is going.\n\n## Output\n\nThe output should contain a single integer — maximal possible total comfort.\n\n[samples]\n\n## Note\n\nIn the first test case best partition into segments is: \\[4, 4\\] \\[2, 5, 2\\] \\[3\\], answer is calculated as follows: 4 + (2 _xor_ 5) + 3 = 4 + 7 + 3 = 14\n\nIn the second test case best partition into segments is: 5 1 \\[3\\] 1 5 \\[2, 4, 2\\] 5, answer calculated as follows: 3 + (2 _xor_ 4) = 3 + 6 = 9.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vladik 经常乘坐火车旅行。他记得一些特别难忘的旅程，我想向你讲述其中一次：\n\nVladik 在初始车站，现在有 #cf_span[n] 个人（包括 Vladik）想要上车。他们已经排成某种顺序，每个人都有一个城市代码 #cf_span[ai]（表示他们要去的城市）。\n\n列车长会选择若干个原有人序列的不相交子段（不需要覆盖整个序列）。同一子段中的人将进入同一节车厢。选择子段的方式需满足：如果至少有一个人要去城市 #cf_span[x]，那么所有要去城市 #cf_span[x] 的人都必须在同一节车厢中。这意味着他们不能属于不同的子段。注意，所有要去城市 #cf_span[x] 的人，要么全部在同一个车厢中，要么全部不上车。\n\n对于从位置 #cf_span[l] 到位置 #cf_span[r] 的子段，其舒适度等于该子段中所有不同城市代码的 _XOR_ 值。_XOR_ 运算也称为异或。\n\n整个列车旅程的总舒适度等于每个子段舒适度的和。\n\n请帮助 Vladik 计算可能的最大总舒适度。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5000]）—— 人数。\n\n第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 5000]），其中 #cf_span[ai] 表示第 #cf_span[i] 个人要去的城市代码。\n\n输出应包含一个整数——可能的最大总舒适度。\n\n在第一个测试用例中，最优的分段方式为：#cf_span[[4, 4]] #cf_span[[2, 5, 2]] #cf_span[[3]]，计算结果为：#cf_span[4 + (2] #cf_span[xor] #cf_span[5) + 3 = 4 + 7 + 3 = 14]\n\n在第二个测试用例中，最优的分段方式为：#cf_span[5] #cf_span[1] #cf_span[[3]] #cf_span[1] #cf_span[5] #cf_span[[2, 4, 2]] #cf_span[5]，计算结果为：#cf_span[3 + (2] #cf_span[xor] #cf_span[4) = 3 + 6 = 9]。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5000]）—— 人数。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 5000]），其中 #cf_span[ai] 表示第 #cf_span[i] 个人要去的城市代码。\n\n## Output\n\n输出应包含一个整数——可能的最大总舒适度。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，最优的分段方式为：#cf_span[[4, 4]] #cf_span[[2, 5, 2]] #cf_span[[3]]，计算结果为：#cf_span[4 + (2] #cf_span[xor] #cf_span[5) + 3 = 4 + 7 + 3 = 14]。在第二个测试用例中，最优的分段方式为：#cf_span[5] #cf_span[1] #cf_span[[3]] #cf_span[1] #cf_span[5] #cf_span[[2, 4, 2]] #cf_span[5]，计算结果为：#cf_span[3 + (2] #cf_span[xor] #cf_span[4) = 3 + 6 = 9]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of people, and let $ a = [a_1, a_2, \\dots, a_n] $ be the sequence of city codes, where $ a_i \\in \\mathbb{Z}_{\\geq 0} $ and $ a_i \\leq 5000 $.\n\nDefine for each city $ c $, the **first occurrence** $ f(c) = \\min\\{ i \\mid a_i = c \\} $ and **last occurrence** $ l(c) = \\max\\{ i \\mid a_i = c \\} $, with $ f(c) = l(c) = \\infty $ if city $ c $ does not appear.\n\nA valid segmentation is a collection of disjoint intervals (segments) $ [l_j, r_j] $ such that for every city $ c $, either:\n- All occurrences of $ c $ are contained within a single segment, or\n- No occurrence of $ c $ is included in any segment.\n\nThat is, for any city $ c $, if $ f(c) $ and $ l(c) $ are finite, then either:\n- $ [f(c), l(c)] \\subseteq [l_j, r_j] $ for some segment $ [l_j, r_j] $, or\n- $ [f(c), l(c)] \\cap \\bigcup_j [l_j, r_j] = \\emptyset $.\n\nFor a segment $ [l, r] $, define its **comfort** as the XOR of all distinct city codes appearing in $ a[l:r+1] $:\n$$\n\\text{comfort}([l, r]) = \\bigoplus_{c \\in \\text{distinct}(a[l:r+1])} c\n$$\n\nThe **total comfort** is the sum of comforts over all selected segments.\n\n**Objective**: Maximize the total comfort over all valid segmentations.\n\nLet $ dp[i] $ denote the maximum total comfort achievable for the prefix $ a[1:i] $ (i.e., first $ i $ people).\n\nWe compute $ dp[i] $ for $ i = 0 $ to $ n $, with $ dp[0] = 0 $.\n\nFor each $ i \\in [1, n] $, we consider all possible ending positions $ j \\in [1, i] $, and check whether the segment $ [j, i] $ can be validly included in a segmentation:\n\n- Let $ S = \\{ a_j, a_{j+1}, \\dots, a_i \\} $ be the set of distinct cities in $ [j, i] $.\n- For each city $ c \\in S $, verify that $ f(c) \\geq j $ and $ l(c) \\leq i $. (I.e., the entire span of each city in $ S $ lies within $ [j, i] $.)\n- If this holds, then $ [j, i] $ is a valid segment, and its comfort is $ \\bigoplus_{c \\in S} c $.\n- Then update:\n  $$\n  dp[i] = \\max\\left( dp[i],\\ dp[j-1] + \\bigoplus_{c \\in \\text{distinct}(a[j:i+1])} c \\right)\n  $$\n\nAdditionally, we may skip person $ i $, so:\n$$\ndp[i] = \\max(dp[i], dp[i-1])\n$$\n\n**Final Answer**: $ dp[n] $\n\n---\n\n**Formal Statement**:\n\nGiven:  \n- Integer $ n \\in [1, 5000] $  \n- Sequence $ a \\in \\{0, 1, \\dots, 5000\\}^n $\n\nDefine for each $ c \\in \\mathbb{Z}_{\\geq 0} $:  \n- $ f(c) = \\min \\{ i \\in [1, n] \\mid a_i = c \\} $ if $ c $ appears, else $ \\infty $  \n- $ l(c) = \\max \\{ i \\in [1, n] \\mid a_i = c \\} $ if $ c $ appears, else $ \\infty $\n\nDefine a segment $ [j, i] $ as **valid** iff:\n$$\n\\forall c \\in \\text{set}(a[j:i+1]), \\quad f(c) \\geq j \\text{ and } l(c) \\leq i\n$$\n\nDefine comfort of valid segment $ [j, i] $ as:\n$$\n\\text{comfort}(j, i) = \\bigoplus_{c \\in \\text{set}(a[j:i+1])} c\n$$\n\nDefine $ dp[0] = 0 $, and for $ i \\in [1, n] $:\n$$\ndp[i] = \\max \\left( dp[i-1],\\ \\max_{\\substack{1 \\leq j \\leq i \\\\ [j,i] \\text{ valid}}} \\left( dp[j-1] + \\text{comfort}(j, i) \\right) \\right)\n$$\n\n**Output**: $ dp[n] $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF811C","tags":["dp","implementation"],"sample_group":[["6\n4 4 2 5 2 3","14"],["9\n5 1 3 1 5 2 4 2 5","9"]],"created_at":"2026-03-03 11:00:39"}}