分数: 1000 点
问题陈述
我们有一场比赛 N 参与者和 N 问题。 参与者已编号 1 通过 N。 对于每一对参与者和一个问题,我们知道参与者解决问题所花费的时间,并且它是 1, 2,或 3 分钟。 其中 N 问题,有 A_i 参与者遇到的问题 i 需要 1 分钟解决, B_i 她/他遇到的问题 2 分钟解决,并且 C_i 她/他遇到的问题 3 分钟解决。
确定以下是否可以对每个成立 1 \leq i, j \leq N 当参与者可以自由决定他们解决问题的顺序时。
- 让 S 是参与者的总时间 i 需要解决第一个问题 i 问题,以及 T 是参与者的总时间 j 需要解决第一个问题 i 问题。那么,我们有 S \leq T.
换句话说,确定参与者是否有可能 i 当他们解决了第一个问题时,排名第一(可能有平局) i 问题,忽略他们在问题之间切换所需的时间。
鉴于 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.
输入
输入由标准输入按以下格式给出。第一行如下:
T
然后, T 测试用例如下,每个测试用例的格式如下:
N A_1 B_1 C_1 : A_N B_N C_N
输出
对于每个测试用例,打印 Yes 如果可以满足问题陈述中的条件,则打印 No 否则。
每个测试用例使用一行。 (检查器不区分大小写:我们接受大写和小写字母。)
示例输入 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 解决了第一个问题 3 分钟,第二个 2 分钟,第三次 2 分钟;
- 参与者 2 解决了第一个问题 3 分钟,第二个 2 分钟,第三次 3 分钟;
- 参与者 3 解决了第一个问题 3 分钟,第二个 2 分钟,第三次 1 分钟。