公式解説では \(K\) の値で場合分けしていますが、この問題は \(O(N \log(ans))\) で解くことができます。

ここでは \(0\)-\(\text{index}\) とします。

まず、\(sum_{i}=\sum_{j=i}^{i+K-1} t_{j}\) とします。

木 \(i\) をカットしたときに、 \(sum\) が変わるindex の最小値を \(L_{i}\)、最大値を \(R_{i}\) とします。\((L_{i}=max(0,i-K+1),R_{i}=min(i,N-K))\)

そして、答えを \(val\) 以下にすることができるかを以下の手順で判定します。

まず、長さ \(N-K+2\) の数列 \(dp\) を用意します。初期値は \(dp_{0}=0\) で、その他の値は大きい値にします。

この \(dp\) を以下のように更新します。

• \(sum_{i}\leq val\) なら \(dp_{i+1}\leftarrow \min(dp_{i+1},dp_[I])\)

• \(\max_{L_{i}\leq j\leq R_{i}}(sum_{j})-t_{i}\leq val\) なら \(dp_{R_{i}+1}\leftarrow \min(dp_{R_{i}+1},dp_{L_{i}}+1)\)

全て更新し終わった後、\(dp_{N-K+1}\leftarrow M\) なら答えを \(val\) 以下にすることが可能です。

以上の更新方法を用いると、\(O(N\log(ans))\) で解けます。

更新方法について説明を加えると、一つ目の更新が区間ないで木を切ったものがいない場合で、二つ目の更新が区間内で木をきった場合です。

一つの区間で木を２つ以上切ることが許されていないため、このような更新が正当性のあるものとなっています。

実装例 c++ 38ms