← 返回题目列表

AtCoder · abc450_b

C. 分割票务

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

分数: 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) 满足条件。