1989C.md (2133B)
1 Source: https://codeforces.com/problemset/problem/1989/C 2 3 C. Two Movies 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 A movie company has released $2$ movies. These $2$ movies were watched by $n$ people. For each person, we know their attitude towards the first movie (liked it, neutral, or disliked it) and towards the second movie. 22 23 If a person is asked to leave a review for the movie, then: 24 25 * if that person liked the movie, they will leave a positive review, and the movie's rating will increase by $1$; 26 * if that person disliked the movie, they will leave a negative review, and the movie's rating will decrease by $1$; 27 * otherwise, they will leave a neutral review, and the movie's rating will not change. 28 29 Every person will review exactly one movie — and for every person, you can choose which movie they will review. 30 31 The company's rating is the minimum of the ratings of the two movies. Your task is to calculate the maximum possible rating of the company. 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 36 37 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$). 38 39 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-1 \le a_i \le 1$), where $a_i$ is equal to $-1$ if the first movie was disliked by the $i$-th viewer; equal to $1$ if the first movie was liked; and $0$ if the attitude is neutral. 40 41 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($-1 \le b_i \le 1$), where $b_i$ is equal to $-1$ if the second movie was disliked by the $i$-th viewer; equal to $1$ if the second movie was liked; and $0$ if the attitude is neutral. 42 43 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, print a single integer — the maximum possible rating of the company, if for each person, choose which movie to leave a review on. 48 49 Example 50 51 Input 52 53 ``` 54 4 55 56 2 57 58 -1 1 59 60 -1 -1 61 62 1 63 64 -1 65 66 -1 67 68 5 69 70 0 -1 1 0 1 71 72 -1 1 0 0 1 73 74 4 75 76 -1 -1 -1 1 77 78 -1 1 1 1 79 ``` 80 81 Output 82 83 ``` 84 0 85 -1 86 1 87 1 88 ```