English · Original
Chinese · Translation
Formal · Original
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.
Output the minimum possible value of error after _k_1 operations on array _A_ and _k_2 operations on array _B_ have been performed.
## Input
The 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.
Second line contains _n_ space separated integers _a_1, _a_2, ..., _a__n_ ( - 106 ≤ _a__i_ ≤ 106) — array _A_.
Third line contains _n_ space separated integers _b_1, _b_2, ..., _b__n_ ( - 106 ≤ _b__i_ ≤ 106)— array _B_.
## Output
Output 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_.
[samples]
## Note
In 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.
In 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.
In 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.
你被给定两个数组 #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]。
请输出在对数组 #cf_span[A] 执行恰好 #cf_span[k1] 次操作、对数组 #cf_span[B] 执行恰好 #cf_span[k2] 次操作后，可能的最小误差值。
第一行包含三个用空格分隔的整数 #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]。
请输出一个整数 —— 在对数组 #cf_span[A] 执行恰好 #cf_span[k1] 次操作、对数组 #cf_span[B] 执行恰好 #cf_span[k2] 次操作后，可能的最小误差值。
在第一个测试用例中，我们无法对 #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]。
## Input
第一行包含三个用空格分隔的整数 #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]。
## Output
请输出一个整数 —— 在对数组 #cf_span[A] 执行恰好 #cf_span[k1] 次操作、对数组 #cf_span[B] 执行恰好 #cf_span[k2] 次操作后，可能的最小误差值。
[samples]
## Note
在第一个测试用例中，我们无法对 #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]。
**Definitions**
Let $ n, k_1, k_2 \in \mathbb{Z}_{\geq 0} $ be given integers.
Let $ 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.
Define the error function:
$$
E(A, B) = \sum_{i=1}^n (a_i - b_i)^2
$$
**Constraints**
1. $ 1 \leq n \leq 10^3 $
2. $ 0 \leq k_1 + k_2 \leq 10^3 $, with $ k_1, k_2 \geq 0 $
3. $ |a_i|, |b_i| \leq 10^6 $ for all $ i \in \{1, \dots, n\} $
**Operations**
- Exactly $ k_1 $ operations may be performed on array $ A $: each operation increments or decrements one element of $ A $ by 1.
- Exactly $ k_2 $ operations may be performed on array $ B $: each operation increments or decrements one element of $ B $ by 1.
Let $ \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:
$$
\sum_{i=1}^n |\delta_i^A| = k_1, \quad \sum_{i=1}^n |\delta_i^B| = k_2
$$
The resulting arrays are:
$ A' = (a_1 + \delta_1^A, \dots, a_n + \delta_n^A) $,
$ B' = (b_1 + \delta_1^B, \dots, b_n + \delta_n^B) $
**Objective**
Minimize the error:
$$
\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
$$
That 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 $.
API Response (JSON)
{
"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 operatio...",
"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] 次操作。在一次操作中，你必须选择数组中的一个元素，并将其增加或减少 #...",
"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...",
"is_translate": false,
"language": "Formal"
}
]
}