/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
N 人の参加者と N 個の問題からなるコンテストがあります。 参加者には 1 から N までの番号が付いています。 各参加者と問題の組について、その参加者がその問題を解くのにかかる時間が分かっており、 その時間は 1 分、2 分または 3 分です。 N 個の問題のうち、参加者 i が解くのに 1 分かかる問題は A_i 問、 2 分かかる問題は B_i 問、3 分かかる問題は C_i 問あります。
各参加者が問題を解く順番を自由に定めることで、すべての 1 \leq i, j \leq N について以下が成立することがありうるか判定してください。
- 参加者 i が最初の i 問を解くのにかかる時間を S 分、参加者 j が最初の i 問を解くのにかかる時間を T 分とする。このとき S \leq T となる。
つまり、すべての i について参加者 i が最初の i 問を解いた時点で 1 位（同率でもよい）となることがありうるか判定してください。 ただし、ある問題を解いてから次の問題にうつるまでにかかる時間は無視できるものとします。
T 個のテストケースが与えられるので、それぞれを解いてください。
制約
- 1 \leq T \leq 2\times 10^5
- 1 \leq N \leq 2\times 10^5
- 0 \leq A_i,B_i,C_i \leq N
- A_i+B_i+C_i=N
- 全テストケースにおける N の総和は 2\times 10^5 以下である。
入力
入力は以下の形式で標準入力から与えられる。入力の 1 行目は次の通りである。
T
そして、以下の形式で T 個のテストケースが続く。
N A_1 B_1 C_1 : A_N B_N C_N
出力
各テストケースについて、問題文の条件が成立しうるならば Yes 、そうでなければ No と出力せよ。
1 行につき 1 個のテストケースへの出力を行え。なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。
入力例 1
2 3 0 2 1 0 1 2 1 1 1 3 0 2 1 0 0 3 1 1 1
出力例 1
Yes No
最初のテストケースでは、例えば以下のような場合に条件が成立します。
- 参加者 1 は 1 問目を 3 分、2 問目を 2 分、3 問目を 2 分かけて解く。
- 参加者 2 は 1 問目を 3 分、2 問目を 2 分、3 問目を 3 分かけて解く。
- 参加者 3 は 1 問目を 3 分、2 問目を 2 分、3 問目を 1 分かけて解く。
Score : 1000 points
Problem Statement
We have a contest with N participants and N problems. The participants are numbered 1 through N. For each pair of a participant and a problem, we know the time it takes for the participant to solve the problem, and it is 1, 2, or 3 minutes. Among the N problems, there are A_i problems that Participant i takes 1 minute to solve, B_i problems that s/he takes 2 minutes to solve, and C_i problems that s/he takes 3 minutes to solve.
Determine whether it is possible for the following to hold for every 1 \leq i, j \leq N when the participants can freely decide the order they solve the problems.
- Let S be the total time Participant i takes to solve the first i problems, and T be the total time Participant j takes to solve the first i problems. Then, we have S \leq T.
In other words, determine whether it is possible that Participant i places first (possibly with ties) when they have solved the first i problems, ignoring the time it takes for them to switch between problems.
Given T test cases, solve each of them.
Constraints
- 1 \leq T \leq 2\times 10^5
- 1 \leq N \leq 2\times 10^5
- 0 \leq A_i,B_i,C_i \leq N
- A_i+B_i+C_i=N
- The sum of N over all test cases is at most 2\times 10^5.
Input
Input is given from Standard Input in the following format. The first line is as follows:
T
Then, T test cases follow, each in the format below:
N A_1 B_1 C_1 : A_N B_N C_N
Output
For each test case, print Yes if the condition in Problem Statement can be satisfied, and print No otherwise.
Use one line for each test case. (The checker is case-insensitive: we will accept both uppercase and lowercase letters.)
Sample Input 1
2 3 0 2 1 0 1 2 1 1 1 3 0 2 1 0 0 3 1 1 1
Sample Output 1
Yes No
In the first test case, one scenario that satisfies the condition is as follows:
- Participant 1 solves the first problem in 3 minutes, the second in 2 minutes, and the third in 2 minutes;
- Participant 2 solves the first problem in 3 minutes, the second in 2 minutes, and the third in 3 minutes;
- Participant 3 solves the first problem in 3 minutes, the second in 2 minutes, and the third in 1 minutes.