codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.