2112C.md (1957B)
1 Source: https://codeforces.com/problemset/problem/2112/C 2 3 C. Coloring Game 4 5 time limit per test 6 7 2.5 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 and Bob are playing a game using an integer array $a$ of size $n$. 22 23 Initially, all elements of the array are colorless. First, Alice chooses $3$ elements and colors them red. Then Bob chooses any element and colors it blue (if it was red — recolor it). Alice wins if the sum of the red elements is strictly greater than the value of the blue element. 24 25 Your task is to calculate the number of ways that Alice can choose $3$ elements in order to win regardless of Bob's actions. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. 30 31 The first line of each test case contains a single integer $n$ ($3 \le n \le 5000$). 32 33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 \le a_2 \le \cdots \le a_n \le 10^5$). 34 35 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $5000$. 36 37 Output 38 39 For each test case, print a single integer — the number of ways that Alice can choose $3$ elements in order to win regardless of Bob's actions. 40 41 Example 42 43 Input 44 45 ``` 46 6 47 48 3 49 50 1 2 3 51 52 4 53 54 1 1 2 4 55 56 5 57 58 7 7 7 7 7 59 60 5 61 62 1 1 2 2 4 63 64 6 65 66 2 3 3 4 5 5 67 68 5 69 70 1 1 1 1 3 71 ``` 72 73 Output 74 75 ``` 76 0 77 0 78 10 79 2 80 16 81 0 82 ``` 83 84 Note 85 86 In the first two test cases, no matter which three elements Alice chooses, Bob will be able to paint one element blue so that Alice does not win. 87 88 In the third test case, Alice can choose any three elements. If Bob colors one of the red elements, the sum of red elements will be $14$, and the sum of blue elements will be $7$. If Bob chooses an uncolored element, the sum of red elements will be $21$, and the sum of blue elements will be $7$. 89 90 In the fourth test case, Alice can choose either the $1$-st, $3$-rd and $4$-th element, or the $2$-nd, $3$-rd and $4$-th element.