{"problem":{"name":"[SDCPC 2023] Matching","description":{"content":"Given an integer sequence $a_1, a_2, \\cdots, a_n$ of length $n$, we construct an undirected graph $G$ from the sequence. More precisely, for all $1 \\le i < j \\le n$, if $i - j = a_i - a_j$, there will","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9562"},"statements":[{"statement_type":"Markdown","content":"Given an integer sequence $a_1, a_2, \\cdots, a_n$ of length $n$, we construct an undirected graph $G$ from the sequence. More precisely, for all $1 \\le i < j \\le n$, if $i - j = a_i - a_j$, there will be an undirected edge in $G$ connecting vertices $i$ and $j$. The weight of the edge is $(a_i + a_j)$.\n\nFind a matching of $G$ so that the sum of weight of all edges in the matching is maximized, and output this maximized sum.\n\nRecall that a matching of an undirected graph means that we choose some edges from the graph such that any two edges have no common vertices. Specifically, not choosing any edge is also a matching.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains an integer $n$ ($2 \\le n \\le 10^5$) indicating the length of the sequence.\n\nThe second line contains $n$ integers $a_1, a_2, \\cdots, a_n$ ($-10^9 \\le a_i \\le 10^9$) indicating the sequence.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $5 \\times 10^5$.\n\n## Output\n\nFor each test case output one line containing one integer indicating the maximum sum of weight of all edges in a matching.\n\n[samples]\n\n## Note\n\nFor the first sample test case, the optimal choice is to choose the three edges connecting vertex $3$ and $5$, vertex $4$ and $7$, and finally vertex $8$ and $9$. The sum of weight is $(5 + 7) + (6 + 9) + (1 + 2) = 30$.\n\nFor the second sample test case, as all edges have negative weights, the optimal matching should not choose any edge. The answer is $0$.\n\nFor the third sample test case, as there is no edge in the graph, the answer is $0$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9562","tags":["贪心","2023","山东","O2优化","省赛/邀请赛"],"sample_group":[["3\n9\n3 -5 5 6 7 -1 9 1 2\n3\n-5 -4 -3\n3\n1 10 100\n","30\n0\n0\n"]],"created_at":"2026-03-03 11:09:25"}}