\(O(N)\) 時間で解くこともできます。

まず、気力回復の上限値を無視して、いくらでも回復できるとして計算します。各テント \(n\) に到達した時点において、

• 気力 \(f(n)\) 以上ならば最後まで辿りつける。そうでなければ辿りつけない。

となる \(f(n)\) が、\(n = N, N-1, \ldots, 1\) 順に計算できます。答は \(\max\{f(N), \ldots, f(1)\}\) です。

実際、\(T < \max\{f(N), \ldots, f(1)\}\) ならば到達不可能であることは、\(T < f(n)\) となる \(n\) をとって、テント \(n\) に到達後のことを考えると分かります。

\(T = \max\{f(N), \ldots, f(1)\}\) とした場合に到達可能であることを確認します。\(f(n)\) の計算方法から

• 気力を捨てることも許すとする。
• このとき、\(n = 1, 2, \ldots\) 順に、テント \(n\) 到達時点で気力がちょうど \(f(n)\) であるように歩くことができる。

ことが確かめられます。気力を捨てることも許してたどり着けるのですから、捨てなければなおさらたどり着けるはずです。

解答例：https://atcoder.jp/contests/utpc2020/submissions/21273939