/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 個の駅 1,2,\dots,N があり、これらはこの順に西から東に一直線上に並んでいます。
AtCoder 鉄道の電車はこれら N 個の駅を通り、西から東に走っています。
1 \leq i \lt j \leq N を満たす任意の 2 整数 i,j について、駅 i から電車に乗って駅 j で降りるのにコストが C_{i,j} かかります。
以下のような 3 つの整数 a,b,c が存在するかを判定してください。
- 1 \leq a \lt b \lt c \leq N
- 駅 a から電車に乗って駅 c で降りるときにかかるコストよりも、駅 a から電車に乗って駅 b で降り、再度、駅 b から電車に乗って駅 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}
出力
条件を満たす 3 整数 a,b,c が存在するならば Yes を、存在しないならば No を 1 行で出力せよ。
入力例 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) を選んでも、条件を満たしません。
Score : 200 points
Problem Statement
There are N stations 1, 2, \dots, N, arranged in a straight line from west to east in this order.
The AtCoder Railway train passes through these N stations and runs from west to east.
For any two integers i, j satisfying 1 \leq i \lt j \leq N, the cost of boarding the train at station i and getting off at station j is C_{i,j}.
Determine whether there exist three integers a, b, c such that:
- 1 \leq a \lt b \lt c \leq N
- The total cost of boarding the train at station a, getting off at station b, then boarding the train again at station b, and getting off at station c is less than the cost of boarding the train at station a and getting off at station c.
Constraints
- 3 \leq N \leq 100
- 1 \leq C_{i,j} \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
C_{1,2} C_{1,3} \dots C_{1,N}
C_{2,3} \dots C_{2,N}
\vdots
C_{N-1,N}
Output
If there exist three integers a, b, c satisfying the conditions, output Yes; otherwise, output No, on a single line.
Sample Input 1
3 45 450 45
Sample Output 1
Yes
Choosing (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
so the conditions are satisfied.
Sample Input 2
4 25 40 65 30 55 25
Sample Output 2
No
No choice of (a, b, c) satisfies the conditions.