← 返回题目列表

AtCoder · agc053_d

D. 每个人都是赢家

中文机器翻译题面 查看原题

分数: 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 分钟。