問題

https://yukicoder.me/problems/no/909

考察

求める最大距離はd = \min_{1 \leq i \leq N}(X_i + Y_i)です。

これ以上大きなd_{NG} > \min_{1 \leq i \leq N}(X_i + Y_i)にはできません。
なぜなら、たぴ0とたぴN+1をd_{NG}離して配置すると、例えば\min_{1 \leq i \leq N}(X_i + Y_i)をみたすたぴi_{min}をどのように配置しても、たぴ0からX_{i_{min}}より大きく離れるか、たぴN+1からY_{i_{min}}より大きく離れるからです。

一方、d = \min_{1 \leq i \leq N}(X_i + Y_i)は以下の構成で達成できます。

たぴ0を0に配置します。
たぴN+1をdに配置します。

たぴi (1 \leq i \leq N)について、

• d \leq X_iのときdに配置します。こうすればたぴ0からX_i以下であり、たぴN+1からの距離は0なのでY_iも自然と満たされます。

• d > X_iのとき、X_iに配置します。このとき、たぴN+1からY_i以下という条件もみたしています。なぜなら、X_i + Y_i \geq dより、Y_i \geq d - X_iだからです。

https://yukicoder.me/submissions/397044