problem.txt (2351B)
1 B. Sequence Decreasing 2 time limit per test1 second 3 memory limit per test256 megabytes 4 5 Gracie Abrams - That's So True 6 An array b 7 of non-negative integers is called good if it can be turned into a non-empty array consisting only of zeros by performing the following operation any number of times (possibly zero): 8 9 choose a non-empty subarray∗ 10 of b 11 in which all elements are positive; 12 decrease each element of this subarray by 1 13 ; 14 choose one element of this subarray and remove it from b 15 , without changing the order of the remaining elements. 16 You are given an array a 17 of n 18 non-negative integers. Find the maximum length of a good subsequence† 19 of a 20 , or report that a 21 has no good subsequence. 22 23 ∗ 24 An array c 25 is a subarray of an array b 26 if c 27 can be obtained from b 28 by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. 29 30 † 31 A sequence c 32 is a subsequence of a sequence a 33 if c 34 can be obtained from a 35 by the deletion of several (possibly, zero or all) elements from arbitrary positions. 36 37 Input 38 Each test contains multiple test cases. The first line contains the number of test cases t 39 (1≤t≤104 40 ). The description of the test cases follows. 41 42 The first line of each test case contains a single integer n 43 (1≤n≤2⋅105 44 ) — the length of the array a 45 . 46 47 The second line of each test case contains n 48 integers a1,a2,…,an 49 (0≤ai≤109 50 ) — the elements of the array a 51 . 52 53 It is guaranteed that the sum of n 54 over all test cases does not exceed 2⋅105 55 . 56 --- 57 58 - thoughts: 59 - good if b -> an array of all zeroes 60 - operation 61 - choose non-empty subarray in which all elements are positive 62 - decrease each element by 1 63 - remove one of these elements from the subarray 64 65 --- 66 67 1 68 0 69 70 return 1 71 72 1 73 1 74 75 return 0 76 77 --- 78 79 3 80 5 3 4 81 82 5,3 -> 2 83 84 2,4 -> 1 85 86 1 -> 87 88 0 89 90 --- 91 92 5 93 2 1 1 0 3 94 95 2 1 1 3 -> 1 0 0 0 96 97 --- 98 99 - so basically can we get to zeroes? 100 - how the fuck does that work? 101 102 --- 103 104 - can we make zeroes? 105 - yes 106 - iteratively select smallest element, matched with one other element and decrement 107 - specifically, yes is true iff the number of non-zero elements >= lowestValue 108 - no 109 - under this case, we know the above conditional is not true 110 - removing elements won't help us so we return 0