分数: 200 点
问题陈述
有 N 站 1, 2, \dots, N,按此顺序从西向东排成一条直线。
AtCoder 铁路列车经过这些 N 车站自西向东运行。
对于任意两个整数 i, j 满意 1 \leq i \lt j \leq N, 车站上车费用 i 并在车站下车 j is C_{i,j}.
判断是否存在三个整数 a, b, c 这样:
- 1 \leq a \lt b \lt c \leq N
- 车站上车总费用 a, 车站下车 b,然后在车站再次登上火车 b,并在车站下车 c 低于车站登车费用 a 并在车站下车 c.
约束
- 3 \leq N \leq 100
- 1 \leq C_{i,j} \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
C_{1,2} C_{1,3} \dots C_{1,N}
C_{2,3} \dots C_{2,N}
\vdots
C_{N-1,N}
输出
如果存在三个整数 a, b, c 满足条件,输出 Yes;否则,输出 No,在一行上。
示例输入 1
3 45 450 45
示例输出 1
Yes
选择 (a, b, c) = (1, 2, 3),
C_{a,b}+C_{b,c}=C_{1,2}+C_{2,3}=45+45
C_{a,c}=C_{1,3}=450
所以条件满足。
示例输入 2
4 25 40 65 30 55 25
示例输出 2
No
没有选择 (a, b, c) 满足条件。