2028C.md (2672B)
1 Source: https://codeforces.com/problemset/problem/2028/C 2 3 C. Alice's Adventures in Cutting Cake 4 5 time limit per test 6 7 2 seconds 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 Alice is at the Mad Hatter's tea party! There is a long sheet cake made up of $n$ sections with tastiness values $a_1, a_2, \ldots, a_n$. There are $m$ creatures at the tea party, excluding Alice. 22 23 Alice will cut the cake into $m + 1$ pieces. Formally, she will partition the cake into $m + 1$ subarrays, where each subarray consists of some number of adjacent sections. The tastiness of a piece is the sum of tastiness of its sections. Afterwards, she will divvy these $m + 1$ pieces up among the $m$ creatures and herself (her piece can be empty). However, each of the $m$ creatures will only be happy when the tastiness of its piece is $v$ or more. 24 25 Alice wants to make sure every creature is happy. Limited by this condition, she also wants to maximize the tastiness of her own piece. Can you help Alice find the maximum tastiness her piece can have? If there is no way to make sure every creature is happy, output $-1$. 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 30 31 The first line of each test case contains three integers $n, m, v$ ($1\le m\le n\le 2\cdot 10^5$; $1\le v\le 10^9$) — the number of sections, the number of creatures, and the creatures' minimum requirement for tastiness, respectively. 32 33 The next line contains $n$ space separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the tastinesses of the sections. 34 35 The sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 36 37 Output 38 39 For each test case, output the maximum tastiness Alice can achieve for her piece, or $-1$ if there is no way to make sure every creature is happy. 40 41 Example 42 43 Input 44 45 ``` 46 7 47 48 6 2 1 49 50 1 1 10 1 1 10 51 52 6 2 2 53 54 1 1 10 1 1 10 55 56 6 2 3 57 58 1 1 10 1 1 10 59 60 6 2 10 61 62 1 1 10 1 1 10 63 64 6 2 11 65 66 1 1 10 1 1 10 67 68 6 2 12 69 70 1 1 10 1 1 10 71 72 6 2 12 73 74 1 1 1 1 10 10 75 ``` 76 77 Output 78 79 ``` 80 22 81 12 82 2 83 2 84 2 85 0 86 -1 87 ``` 88 89 Note 90 91 For the first test case, Alice can give the first and second section as their own pieces, and then take the remaining $10 + 1 + 1 + 10 = 22$ tastiness for herself. We can show that she cannot do any better. 92 93 For the second test case, Alice could give the first and second section as one piece, and the sixth section as one piece. She can then take the remaining $10 + 1 + 1 = 12$ tastiness for herself. We can show that she cannot do any better. 94 95 For the seventh test case, Alice cannot give each creature a piece of at least $12$ tastiness.