CF2029I Variance Challenge

Kevin has recently learned the definition of variance. For an array $ a $ of length $ n $ , the variance of $ a $ is defined as follows: - Let $ x=\dfrac{1}{n}\displaystyle\sum_{i=1}^n a_i $ , i.e., $ x $ is the mean of the array $ a $ ; - Then, the variance of $ a $ is $ $$$ V(a)=\frac{1}{n}\sum_{i=1}^n(a_i-x)^2. $ $

Now, Kevin gives you an array $ a $ consisting of $ n $ integers, as well as an integer $ k $ . You can perform the following operation on $ a $ :

• Select an interval $ \[l,r\] $ ( $ 1\\le l\\le r\\le n $ ), then for each $ l\\le i\\le r $ , increase $ a\_i $ by $ k $ .

For each $ 1\\le p\\le m $ , you have to find the minimum possible variance of $ a $ after exactly $ p $ operations are performed, independently for each $ p $ .

For simplicity, you only need to output the answers multiplied by $ n^2$$$. It can be proven that the results are always integers.

Each test contains multiple test cases. The first line of the input contains a single integer $ t $ ( $ 1\le t\le 100 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains three integers $ n $ , $ m $ , and $ k $ ( $ 1\le n,m\le 5000 $ , $ \color{red}{n\cdot m\le 2\cdot 10^4} $ , $ 1\le k\le 10^5 $ ) — the length of the array $ a $ , the maximum number of operations, and the number you add to $ a_i $ each time, respectively. The second line contains $ n $ integers $ a_1,a_2,\ldots, a_n $ ( $ 1\le a_i\le 10^5 $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n\cdot m $ over all tests does not exceed $ 2\cdot 10^4 $ .

For each test case, output $ m $ integers in a single line, the $ p $ -th integer denoting the minimum possible variance of $ a $ when exactly $ p $ operations are performed, multiplied by $ n^2 $ .

In the first test case: - For $ p = 1 $ , you can perform the operation on $ [1, 1] $ , changing $ a $ from $ [1, 2, 2] $ to $ [2, 2, 2] $ . Since all of the elements are equal, the variance is equal to $ 0 $ . - For $ p = 2 $ , you can perform the operation on $ [1, 3] $ and then $ [1, 1] $ , changing $ a $ from $ [1, 2, 2] $ to $ [2, 3, 3] $ to $ [3, 3, 3] $ . Since all of the elements are equal, the variance is equal to $ 0 $ . In the second test case, some possible optimal choices are: - $ p=1 $ : $ [\underline{1,}\,2,2]\to [3,2,2] $ ; - $ p=2 $ : $ [1,\underline{2,2}] \to [\underline{1,}\,4,4] \to [3,4,4] $ . In the third test case, some possible optimal choices are: - $ p=1 $ : $ [10,\underline{1,1,1,1,10,1,1,1,1}]\to[10,2,2,2,2,11,2,2,2,2] $ ; - $ p=2 $ : $ [10,1,1,1,1,10,\underline{1,1,1,1}] \to [10,\underline{1,1,1,1},10,2,2,2,2] \to [10,2,2,2,2,10,2,2,2,2] $ . In the eighth test case, the optimal choice for all $ p $ is to perform the operation on the whole array $ p $ times.