2222C.md (2380B)
1 Source: https://codeforces.com/problemset/problem/2222/C 2 3 C. Median Partition 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 You are given an array $a$ with an odd length $n$ consisting of positive integers. You are required to partition the sequence into several subarrays$^{\text{∗}}$ with odd lengths and the same median$^{\text{†}}$. Your task is to find the maximum number of subarrays. 22 23 More formally, you are required to find a strictly-increasing sequence $k$ with a length of $(p+1)$ where $k_1=1$ and $k_{p+1}=n+1$, such that for every $1\le i\le p$, the medians of the sequences $[a_{k_i},a_{k_i+1},\ldots,a_{k_{i+1}-1}]$ are all the same. The parity of $k_i$ and $k_{i+1}$ should be different. Your task is to find the biggest possible value of $p$. 24 25 $^{\text{∗}}$An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. 26 27 $^{\text{†}}$The median of an array with an odd length $x$ is the $\lceil\frac{x}{2}\rceil$-th element of the array after it is sorted in non-decreasing order. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows. 32 33 The first line of each test case contains a single integer $n$ ($1\le n \lt 5000$, $n$ is odd) — the length of $a$. 34 35 The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$) — the elements of $a$. 36 37 It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5000^2$. 38 39 Output 40 41 For each test case, output a single integer — the maximum number of subarrays. 42 43 Example 44 45 Input 46 47 ``` 48 10 49 50 5 51 52 3 3 2 4 3 53 54 7 55 56 9 5 7 7 4 7 7 57 58 9 59 60 1 1 1 1 1 1 1 1 1 61 62 1 63 64 5 65 66 3 67 68 1 2 3 69 70 3 71 72 2 2 2 73 74 5 75 76 1 2 3 4 5 77 78 5 79 80 2 1 3 2 2 81 82 7 83 84 2 2 1 2 3 2 2 85 86 9 87 88 2 1 2 3 2 1 2 3 2 89 ``` 90 91 Output 92 93 ``` 94 3 95 96 3 97 98 9 99 100 1 101 102 1 103 104 3 105 106 1 107 108 3 109 110 5 111 112 5 113 ``` 114 115 Note 116 117 In the first test case, it is optimal to partition $a$ into $[\underline 3, \underline 3, \underline{2, 4, 3}]$. 118 119 In the second test case, it is optimal to partition $a$ into $[\underline{9, 5, 7}, \underline 7, \underline{4, 7, 7}]$. 120 121 In the third test case, since all the elements are the same, you can partition each element into a separate subarray.