2104B.md (2747B)
1 Source: https://codeforces.com/problemset/problem/2104/B 2 3 B. Move to the End 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ consisting of $n$ integers. 22 23 For every integer $k$ from $1$ to $n$, you have to do the following: 24 25 1. choose an arbitrary element of $a$ and move it to the right end of the array (you can choose the last element, then the array won't change); 26 2. print the sum of $k$ last elements of $a$; 27 3. move the element you've chosen on the first step to its original position (restore the original array $a$). 28 29 For every $k$, you choose the element which you move so that the value you print is the maximum possible. 30 31 Calculate the value you print for every $k$. 32 33 Input 34 35 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 36 37 Each test case consists of two lines: 38 39 * the first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$); 40 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). 41 42 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, print $n$ integers. The $i$-th of these integers should be equal to the maximum value you can print if $k=i$. 47 48 Example 49 50 Input 51 52 ``` 53 4 54 55 7 56 57 13 5 10 14 8 15 13 58 59 6 60 61 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 62 63 1 64 65 42 66 67 2 68 69 7 5 70 ``` 71 72 Output 73 74 ``` 75 15 28 42 50 63 73 78 76 1000000000 2000000000 3000000000 4000000000 5000000000 6000000000 77 42 78 7 12 79 ``` 80 81 Note 82 83 Let's consider the first test case from the statement: 84 85 * when $k = 1$, you can move the $6$-th element to the end, the array becomes $[13, 5, 10, 14, 8, 13, 15]$, and the value you print is $15$; 86 * when $k = 2$, you can move the $6$-th element to the end, the array becomes $[13, 5, 10, 14, 8, 13, 15]$, and the value you print is $13 + 15 = 28$; 87 * when $k = 3$, you can move the $4$-th element to the end, the array becomes $[13, 5, 10, 8, 15, 13, 14]$, and the value you print is $15 + 13 + 14 = 42$; 88 * when $k = 4$, you can move the $5$-th element to the end, the array becomes $[13, 5, 10, 14, 15, 13, 8]$, and the value you print is $14 + 15 + 13 + 8 = 50$; 89 * when $k = 5$, you can move the $1$-st element to the end, the array becomes $[5, 10, 14, 8, 15, 13, 13]$, and the value you print is $14 + 8 + 15 + 13 + 13 = 63$; 90 * when $k = 6$, you can move the $1$-st element to the end, the array becomes $[5, 10, 14, 8, 15, 13, 13]$, and the value you print is $10 + 14 + 8 + 15 + 13 + 13 = 73$; 91 * when $k = 7$, you can move the $6$-th element to the end, the array becomes $[13, 5, 10, 14, 8, 13, 15]$, and the value you print is $13 + 5 + 10 + 14 + 8 + 13 + 15 = 78$.