問題一覧 > 通常問題

No.1925 悪鬼三七次元

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : 37zigen37zigen / テスター : tassei903tassei903
3 ProblemId : 3447 / 自分の提出
問題文最終更新日: 2022-05-02 00:26:25

問題文

悪鬼三七次元に追われ、一次元に迷い込んだ YUKI は、零次元に亡命しようとしています。しかし、零次元で生きられるのは、単細胞生物だけです。

YUKI は $x_1, x_2, \ldots, x_{N+1}$ (昇順)に細胞壁を持っています。 YUKI の細胞は、細胞壁を2つ含む極小な区間のことで、$[x_1, x_2], [x_2, x_3], \ldots, [x_N, x_{N+1}]$ の $N$ 個です。

細胞が一つになるまで、YUKI と三七次元は交互に細胞壁を一つ選んで破壊します。例えば、二つの細胞 $[1, 2], [2, 3]$ は細胞壁 $2$ を破壊すると、一つの細胞 $[1, 3]$ になります。 YUKI が先手、三七次元が後手です。 三七次元は最後の細胞の大きさをできるだけ小さくしたく、YUKI は最後の細胞の大きさをできるだけ大きくしたいです。 両者が最適に行動したときの、最後の細胞の大きさを求めてください。

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

$A_i = x_{i+1}-x_i$ で定義される数列 $A$ が与えられます。

  • 入力は全て整数
  • $1 \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^9$

出力

最後の細胞の大きさを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
1
10
出力
10

最初から一つしか細胞はありません。

サンプル2
入力
2
1 10
出力
11

サンプル3
入力
3
1 10 100
出力
11

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。