codeforces-scrape

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

1946B.md (3259B)


      1 Source: https://codeforces.com/problemset/problem/1946/B
      2 
      3 B. Maximum Sum
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You have an array $a$ of $n$ integers.
     22 
     23 You perform exactly $k$ operations on it. In one operation, you select any contiguous subarray of the array $a$ (possibly empty) and insert the sum of this subarray anywhere in the array.
     24 
     25 Your task is to find the maximum possible sum of the array after $k$ such operations.
     26 
     27 As this number can be very large, output the answer modulo $10^9 + 7$.
     28 
     29 Reminder: the remainder of a number $x$ modulo $p$ is the smallest non-negative $y$ such that there exists an integer $q$ and $x = p \cdot q + y$.
     30 
     31 Input
     32 
     33 Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follows the description of the test cases.
     34 
     35 The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 2 \cdot 10^5$) — the length of the array $a$ and the number of operations, respectively.
     36 
     37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the array $a$ itself.
     38 
     39 It is guaranteed that the sum of the values of $n$ and $k$ for all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test, output a single integer — the maximum sum of the array that can be obtained after $k$ operations modulo $10^9 + 7$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 12
     51 
     52 2 2
     53 
     54 -4 -7
     55 
     56 3 3
     57 
     58 2 2 8
     59 
     60 1 7
     61 
     62 7
     63 
     64 5 1
     65 
     66 4 -2 8 -12 9
     67 
     68 7 4
     69 
     70 8 14 -9 6 0 -1 3
     71 
     72 7 100
     73 
     74 5 3 -8 12 -5 -9 3
     75 
     76 6 1000
     77 
     78 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000
     79 
     80 2 1
     81 
     82 1000000000 8
     83 
     84 5 4
     85 
     86 0 0 0 0 0
     87 
     88 6 10
     89 
     90 48973 757292 58277 -38574 27475 999984
     91 
     92 7 1
     93 
     94 -1000 1000 -1000 1000 -1000 1000 -1000
     95 
     96 10 10050
     97 
     98 408293874 -3498597 7374783 295774930 -48574034 26623784 498754833 -294875830 283045804 85938045
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 999999996
    105 96
    106 896
    107 17
    108 351
    109 716455332
    110 42
    111 2
    112 0
    113 897909241
    114 0
    115 416571966
    116 ```
    117 
    118 Note
    119 
    120 In the first test case, it is advantageous to take an empty subarray of the array twice and insert the sum of the empty subarray (zero) anywhere, then the sum of the resulting array will be $(-4) + (-7) + 0 + 0 = -11$, modulo $10^9 + 7$ this is $999\,999\,996$.
    121 
    122 In the second test case, it is advantageous to take the sum of the entire array three times and place it anywhere in the array, then one of the possible sequences of actions: [$2, 2, 8$] $\rightarrow$ [$2, 2, 8, 12$] $\rightarrow$ [$2, 2, 8, 12, 24$] $\rightarrow$ [$2, 2, 8, 12, 24, 48$], the sum of the final array is $2 + 2 + 8 + 12 + 24 + 48 = 96$.
    123 
    124 In the fourth test case, it is advantageous to take a subarray of the array consisting of the first three numbers (i.e. consisting of the numbers $4, -2$ and $8$) and insert its sum at the beginning of the array, thereby obtaining the array [$10, 4, -2, 8, -12, 9$], the sum of this array is $17$.
    125 
    126 In the seventh test case, it will always be advantageous for us to take an empty subarray of the array. In this case, the sum of the resulting array will not differ from the sum of the original. The answer will be the sum of the original array, taken modulo — $42$, because $(-6 \cdot (10^9 + 7) + 42 = -6\,000\,000\,000)$.