(略解です。正式な解説は後日公開されます。)

グラフを観察すると次の事実がわかる：

\(f_{L,R}(x)\) を「\(L\) 日目から \(R\) 日目までに \(x\) 円払った時に期間内で得られる経験値の最大値」とする。
\(x\) の偶奇で点を別個に取り出す。形式的に述べると、\(g_{L,R}(x) = f_{L,R}(2x), h_{L,R}(x)=f_{L,R}(2x+1)\) とする。(\(x\) は整数しか取れない)
この時 \(g_{L,R}(x), h_{L,R}(x)\) は上に凸な関数になる。

言い換えると偶奇で数列を分けた時に各数列は凸になるということである。証明は \(f(x)+f(x+4) \leq 2 f (x+2)\) を示すことで従う。
この事実を用いると max-plus convolution を利用して数列をセグ木状にマージしていくことが可能になり、部分点を取ることが出来る。

満点解法について、想定解は Alien DP でクエリあたり \(\mathrm{O}(\log^3 N)\) で解いている。