{"problem":{"name":"I. Array Negations","description":{"content":"You are given an array $a$ of $n$ integers, and an integer $k$. You have to make $k$ negation operations such that at each operation you need to choose an element $a_i$ from the array and replace it w","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10215I"},"statements":[{"statement_type":"Markdown","content":"You are given an array $a$ of $n$ integers, and an integer $k$. You have to make $k$ negation operations such that at each operation you need to choose an element $a_i$ from the array and replace it with $-a_i$.\n\nYour task is to find the optimal way to make the $k$ negation operations such that at the end the sum of the array $a$ is as maximal as possible. Can you?\n\nThe first line contains an integer $T$ ($1 <= T <= 100$) specifying the number of test cases.\n\nThe first line of each test case contains two integers $n$ and $k$ ($1 <= n <= 10^4$, $0 <= k <= 10^4$), in which $n$ is the size of the array, and $k$ is the number of negation operations to be made.\n\nThen a line follows contains $n$ integers $a_1, \\\\\\\\cdots, a_n$ ($-100 <= a_i <= 100$), giving the array $a$.\n\nFor each test case, print a single line containing the maximum sum of array $a$ after making the required number of negation operations.\n\nIn the first test case, the optimal way is to make the negation operation on $a_3$. After this, the array will be = $[ 4, 6, -2 ]$, and its sum is $8$.\n\n## Input\n\nThe first line contains an integer $T$ ($1 <= T <= 100$) specifying the number of test cases.The first line of each test case contains two integers $n$ and $k$ ($1 <= n <= 10^4$, $0 <= k <= 10^4$), in which $n$ is the size of the array, and $k$ is the number of negation operations to be made.Then a line follows contains $n$ integers $a_1, \\\\\\\\cdots, a_n$ ($-100 <= a_i <= 100$), giving the array $a$.\n\n## Output\n\nFor each test case, print a single line containing the maximum sum of array $a$ after making the required number of negation operations.\n\n[samples]\n\n## Note\n\nIn the first test case, the optimal way is to make the negation operation on $a_3$. After this, the array will be = $[ 4, 6, -2 ]$, and its sum is $8$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ j \\in \\{1, \\dots, T\\} $:  \n- Let $ n_j \\in \\mathbb{Z} $ be the size of the array.  \n- Let $ k_j \\in \\mathbb{Z} $ be the number of negation operations.  \n- Let $ A_j = (a_{j,1}, a_{j,2}, \\dots, a_{j,n_j}) $ be the array of integers.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each $ j \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_j \\le 10^4 $  \n   - $ 0 \\le k_j \\le 10^4 $  \n   - $ -100 \\le a_{j,i} \\le 100 $ for all $ i \\in \\{1, \\dots, n_j\\} $  \n\n**Objective**  \nFor each test case $ j $, maximize the sum $ S_j = \\sum_{i=1}^{n_j} a_{j,i} $ after applying exactly $ k_j $ negation operations, where each operation flips the sign of one element $ a_{j,i} \\leftarrow -a_{j,i} $.  \n\nLet $ x_i \\in \\{0,1\\} $ indicate whether element $ a_{j,i} $ is negated an odd number of times (1) or not (0). Then the final sum is:  \n$$\nS_j = \\sum_{i=1}^{n_j} (-1)^{x_i} a_{j,i}\n$$  \nsubject to $ \\sum_{i=1}^{n_j} x_i \\equiv k_j \\pmod{2} $ and $ \\sum_{i=1}^{n_j} x_i \\le k_j $, with the goal of maximizing $ S_j $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10215I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}