{"problem":{"name":"B. Minimize the error","description":{"content":"You are given two arrays _A_ and _B_, each of size _n_. The error, _E_, between these two arrays is defined . You have to perform **exactly** _k_1 operations on array _A_ and **exactly** _k_2 operatio","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF960B"},"statements":[{"statement_type":"Markdown","content":"You are given two arrays _A_ and _B_, each of size _n_. The error, _E_, between these two arrays is defined . You have to perform **exactly** _k_1 operations on array _A_ and **exactly** _k_2 operations on array _B_. In one operation, you have to choose one element of the array and increase or decrease it by 1.\n\nOutput the minimum possible value of error after _k_1 operations on array _A_ and _k_2 operations on array _B_ have been performed.\n\n## Input\n\nThe first line contains three space-separated integers _n_ (1 ≤ _n_ ≤ 103), _k_1 and _k_2 (0 ≤ _k_1 + _k_2 ≤ 103, _k_1 and _k_2 are non-negative) — size of arrays and number of operations to perform on _A_ and _B_ respectively.\n\nSecond line contains _n_ space separated integers _a_1, _a_2, ..., _a__n_ ( - 106 ≤ _a__i_ ≤ 106) — array _A_.\n\nThird line contains _n_ space separated integers _b_1, _b_2, ..., _b__n_ ( - 106 ≤ _b__i_ ≤ 106)— array _B_.\n\n## Output\n\nOutput a single integer — the minimum possible value of after doing exactly _k_1 operations on array _A_ and exactly _k_2 operations on array _B_.\n\n[samples]\n\n## Note\n\nIn the first sample case, we cannot perform any operations on _A_ or _B_. Therefore the minimum possible error _E_ = (1 - 2)2 + (2 - 3)2 = 2.\n\nIn the second sample case, we are required to perform exactly one operation on _A_. In order to minimize error, we increment the first element of _A_ by 1. Now, _A_ = \\[2, 2\\]. The error is now _E_ = (2 - 2)2 + (2 - 2)2 = 0. This is the minimum possible error obtainable.\n\nIn the third sample case, we can increase the first element of _A_ to 8, using the all of the 5 moves available to us. Also, the first element of _B_ can be reduced to 8 using the 6 of the 7 available moves. Now _A_ = \\[8, 4\\] and _B_ = \\[8, 4\\]. The error is now _E_ = (8 - 8)2 + (4 - 4)2 = 0, but we are still left with 1 move for array _B_. Increasing the second element of _B_ to 5 using the left move, we get _B_ = \\[8, 5\\] and _E_ = (8 - 8)2 + (4 - 5)2 = 1.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定两个数组 #cf_span[A] 和 #cf_span[B]，每个数组的大小为 #cf_span[n]。这两个数组之间的误差 #cf_span[E] 定义为 。你需要对数组 #cf_span[A] 执行 *恰好* #cf_span[k1] 次操作，对数组 #cf_span[B] 执行 *恰好* #cf_span[k2] 次操作。在一次操作中，你必须选择数组中的一个元素，并将其增加或减少 #cf_span[1]。\n\n请输出在对数组 #cf_span[A] 执行恰好 #cf_span[k1] 次操作、对数组 #cf_span[B] 执行恰好 #cf_span[k2] 次操作后，可能的最小误差值。\n\n第一行包含三个用空格分隔的整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 103])、#cf_span[k1] 和 #cf_span[k2] (#cf_span[0 ≤ k1 + k2 ≤ 103]，#cf_span[k1] 和 #cf_span[k2] 为非负数) —— 数组的大小以及分别对 #cf_span[A] 和 #cf_span[B] 执行的操作次数。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 106 ≤ ai ≤ 106]) —— 数组 #cf_span[A]。\n\n第三行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, b2, ..., bn] (#cf_span[ - 106 ≤ bi ≤ 106]) —— 数组 #cf_span[B]。\n\n请输出一个整数 —— 在对数组 #cf_span[A] 执行恰好 #cf_span[k1] 次操作、对数组 #cf_span[B] 执行恰好 #cf_span[k2] 次操作后，可能的最小误差值。\n\n在第一个测试用例中，我们无法对 #cf_span[A] 或 #cf_span[B] 执行任何操作。因此最小可能误差为 #cf_span[E = (1 - 2)2 + (2 - 3)2 = 2]。\n\n在第二个测试用例中，我们需要对 #cf_span[A] 执行恰好一次操作。为了最小化误差，我们将 #cf_span[A] 的第一个元素增加 #cf_span[1]。此时，#cf_span[A = [2, 2]]。误差变为 #cf_span[E = (2 - 2)2 + (2 - 2)2 = 0]。这是可获得的最小误差。\n\n在第三个测试用例中，我们可以利用全部 #cf_span[5] 次操作将 #cf_span[A] 的第一个元素增加到 #cf_span[8]。同时，我们可以利用 #cf_span[7] 次操作中的 #cf_span[6] 次将 #cf_span[B] 的第一个元素减少到 #cf_span[8]。此时，#cf_span[A = [8, 4]] 且 #cf_span[B = [8, 4]]。误差变为 #cf_span[E = (8 - 8)2 + (4 - 4)2 = 0]，但我们仍剩下 #cf_span[1] 次对数组 #cf_span[B] 的操作。利用剩余的这一次操作将 #cf_span[B] 的第二个元素增加到 #cf_span[5]，得到 #cf_span[B = [8, 5]]，此时误差为 #cf_span[E = (8 - 8)2 + (4 - 5)2 = 1]。\n\n## Input\n\n第一行包含三个用空格分隔的整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 103])、#cf_span[k1] 和 #cf_span[k2] (#cf_span[0 ≤ k1 + k2 ≤ 103]，#cf_span[k1] 和 #cf_span[k2] 为非负数) —— 数组的大小以及分别对 #cf_span[A] 和 #cf_span[B] 执行的操作次数。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 106 ≤ ai ≤ 106]) —— 数组 #cf_span[A]。第三行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, b2, ..., bn] (#cf_span[ - 106 ≤ bi ≤ 106]) —— 数组 #cf_span[B]。\n\n## Output\n\n请输出一个整数 —— 在对数组 #cf_span[A] 执行恰好 #cf_span[k1] 次操作、对数组 #cf_span[B] 执行恰好 #cf_span[k2] 次操作后，可能的最小误差值。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，我们无法对 #cf_span[A] 或 #cf_span[B] 执行任何操作。因此最小可能误差为 #cf_span[E = (1 - 2)2 + (2 - 3)2 = 2]。在第二个测试用例中，我们需要对 #cf_span[A] 执行恰好一次操作。为了最小化误差，我们将 #cf_span[A] 的第一个元素增加 #cf_span[1]。此时，#cf_span[A = [2, 2]]。误差变为 #cf_span[E = (2 - 2)2 + (2 - 2)2 = 0]。这是可获得的最小误差。在第三个测试用例中，我们可以利用全部 #cf_span[5] 次操作将 #cf_span[A] 的第一个元素增加到 #cf_span[8]。同时，我们可以利用 #cf_span[7] 次操作中的 #cf_span[6] 次将 #cf_span[B] 的第一个元素减少到 #cf_span[8]。此时，#cf_span[A = [8, 4]] 且 #cf_span[B = [8, 4]]。误差变为 #cf_span[E = (8 - 8)2 + (4 - 4)2 = 0]，但我们仍剩下 #cf_span[1] 次对数组 #cf_span[B] 的操作。利用剩余的这一次操作将 #cf_span[B] 的第二个元素增加到 #cf_span[5]，得到 #cf_span[B = [8, 5]]，此时误差为 #cf_span[E = (8 - 8)2 + (4 - 5)2 = 1]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k_1, k_2 \\in \\mathbb{Z}_{\\geq 0} $ be given integers.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ and $ B = (b_1, b_2, \\dots, b_n) \\in \\mathbb{Z}^n $ be two arrays.  \nDefine the error function:  \n$$\nE(A, B) = \\sum_{i=1}^n (a_i - b_i)^2\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^3 $  \n2. $ 0 \\leq k_1 + k_2 \\leq 10^3 $, with $ k_1, k_2 \\geq 0 $  \n3. $ |a_i|, |b_i| \\leq 10^6 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Operations**  \n- Exactly $ k_1 $ operations may be performed on array $ A $: each operation increments or decrements one element of $ A $ by 1.  \n- Exactly $ k_2 $ operations may be performed on array $ B $: each operation increments or decrements one element of $ B $ by 1.  \n\nLet $ \\Delta A = (\\delta_1^A, \\dots, \\delta_n^A) \\in \\mathbb{Z}^n $ and $ \\Delta B = (\\delta_1^B, \\dots, \\delta_n^B) \\in \\mathbb{Z}^n $ be the total changes applied to $ A $ and $ B $, respectively, such that:  \n$$\n\\sum_{i=1}^n |\\delta_i^A| = k_1, \\quad \\sum_{i=1}^n |\\delta_i^B| = k_2\n$$\n\nThe resulting arrays are:  \n$ A' = (a_1 + \\delta_1^A, \\dots, a_n + \\delta_n^A) $,  \n$ B' = (b_1 + \\delta_1^B, \\dots, b_n + \\delta_n^B) $\n\n**Objective**  \nMinimize the error:  \n$$\n\\min_{\\substack{\\Delta A, \\Delta B \\\\ \\sum |\\delta_i^A| = k_1 \\\\ \\sum |\\delta_i^B| = k_2}} \\sum_{i=1}^n \\left( (a_i + \\delta_i^A) - (b_i + \\delta_i^B) \\right)^2\n$$  \nThat is, minimize $ \\sum_{i=1}^n (a_i - b_i + \\delta_i^A - \\delta_i^B)^2 $ subject to the total variation constraints on $ \\Delta A $ and $ \\Delta B $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF960B","tags":["data structures","greedy","sortings"],"sample_group":[["2 0 0\n1 2\n2 3","2"],["2 1 0\n1 2\n2 2","0"],["2 5 7\n3 4\n14 4","1"]],"created_at":"2026-03-03 11:00:39"}}