/ 
Time Limit: 5 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
数列 A=(A_1,\dots,A_N), B=(B_1,\dots,B_N) があります。これらに対して、以下の 3 種類の操作を、任意の順番で任意の回数だけ行うことができます。
- A_i = -1 を満たす i を選び、A_i を任意の非負整数に置き換える。
- B_i = -1 を満たす i を選び、B_i を任意の非負整数に置き換える。
- 数列 A の要素を任意の順番に並び替える。
操作の結果、A, B の全ての要素が非負であり、なおかつ A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N となるようにできるかを判定してください。
制約
- 2 \leq N \leq 2000
- -1 \leq A_i \leq 10^9
- -1 \leq B_i \leq 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
操作の結果、A, B の全ての要素が非負かつ A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N となるようにできる場合は Yes、そうでない場合は No を出力せよ。
入力例 1
4 2 0 -1 3 3 -1 4 2
出力例 1
Yes
以下の操作を行うことを考えます。
- A_3 を 1 に置き換える。
- B_2 を 1 に置き換える。
- A を並び替えて (1,3,0,2) にする。
操作の結果、A = (1,3,0,2), B = (3,1,4,2) となり、A, B の全ての要素が非負かつ A_1+B_1 = A_2+B_2 = A_3+B_3 = A_4+B_4 = 4 が満たされます。
入力例 2
3 1 2 3 1 2 4
出力例 2
No
どのように操作を行っても、A_1+B_1 = A_2+B_2 = A_3+B_3 を満たすようにはできません。
入力例 3
3 1 2 -1 1 2 4
出力例 3
No
Score : 500 points
Problem Statement
There are two sequences A=(A_1,\dots,A_N) and B=(B_1,\dots,B_N). You can perform the following three types of operations any number of times in any order:
- Choose an index i such that A_i = -1, and replace A_i with any non-negative integer.
- Choose an index i such that B_i = -1, and replace B_i with any non-negative integer.
- Rearrange the elements of sequence A in any order.
Determine whether it is possible, after these operations, for all elements of A and B to be non-negative and satisfy A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N.
Constraints
- 2 \leq N \leq 2000
- -1 \leq A_i \leq 10^9
- -1 \leq B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
If it is possible, after the operations, for all elements of A and B to be non-negative and satisfy A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N, print Yes. Otherwise, print No.
Sample Input 1
4 2 0 -1 3 3 -1 4 2
Sample Output 1
Yes
Consider the following operations:
- Replace A_3 with 1.
- Replace B_2 with 1.
- Rearrange A to (1,3,0,2).
After these operations, A = (1,3,0,2) and B = (3,1,4,2): all elements of A and B are non-negative, and A_1+B_1 = A_2+B_2 = A_3+B_3 = A_4+B_4 = 4 is satisfied.
Sample Input 2
3 1 2 3 1 2 4
Sample Output 2
No
No matter how you perform the operations, it is impossible to satisfy A_1+B_1 = A_2+B_2 = A_3+B_3.
Sample Input 3
3 1 2 -1 1 2 4
Sample Output 3
No