要素の総和が \(S\) 以上になる連続部分列はできるだけ少ない要素で作り，残りの部分列はできるだけ細かく分割するのがよさそうです．これを定式化します．

連続部分列 \(A[i,j]\) のコストを \(j-i\) と置くことにします． 要素の総和が \(S\) 以上になる連続部分列を disjoint に \(x\) 個とったとき，そのコストの総和の最小値としてありうる値を \(f(x)\) と置くことにします．

答えを \(x\) 以上にできるか？という問題を考えます． 必要十分条件は，\(x \leq K\) かつ \(f(x) \leq N-K\) です．

ここで，\(f(x)\) は下に凸な関数になります． まずはこれを証明しておきます．

要素の総和が \(S\) 以上になる連続部分列のうち，極小なものだけを考えればよいです． 極小なものが \(m\) 個あったとします．この \(m\) 個の部分列を左から順に \(B_1,B_2,\cdots,B_m\) と呼ぶことにして，\(B_i\) のコストを \(C_i\) とおきます．\(B_i\) たちは極小なので包含関係が存在せず，自然に左右の順序が決定されることに注意してください．

\(f(p)\) の最適解で選んだ部分列の添字を \(x_1 \leq \cdots \leq x_p\) とします． 同様に，\(f(p+2)\) の最適解で選んだ部分列の添字を \(y_1 \leq \cdots \leq y_{p+2}\) とします． この \(2\) つの添字列を適切に入れ替えることで，サイズ \(p+1\) の valid な解を \(2\) つ作ることができます． 例えば，\(x_i \leq y_{i+1} \leq y_{i+2} \leq x_{i+1}\) なる \(i\) が存在するときは，\((x_1,\cdots,x_i,y_{i+2},\cdots,y_{p+2})\) と \((y_1,\cdots,y_{i+1},x_{i+1},\cdots,y_{p+2})\) に組み換えればよいです． 実は，番兵として \(x_0=y_0=0\)，\(x_{p+1}=y_{p+3}=m+1\) を考えると必ず上記の条件を満たす \(i\) が存在することが示せます．詳細は省略しますが，index ごとに \((y\) の個数 \(-x\) の個数 \()\) を考えるとよいです．

以上より，\(2f(p+1) \leq (2\) つのサイズ \(p+1\) の解のコストの和 \()= f(p)+f(p+2)\) となり，\(f\) の凸性が示されました．

\(f\) が凸だとわかれば，俗に Alien DP と呼ばれるテクニックで解くことができます． この部分の解説は他の記事に譲ることにします． 例えば ABC 218 H の解説等が参考になります． なお，Alien DP は Monge 性の成り立つ場面で適用される機会が多いですが，この問題では Monge 性は成立していないことに注意してください．

ところで，この問題で必要なのは \(f(x) \leq N-K\) を満たす最大の \(x\) であって，\(f(x)\) の値そのものではありません． これを解決する一つのやり方は，\(x\) で二分探索することです．計算量が \(O(\log N)\) 倍されてしまいますが，定数倍が悪くなければこれでも AC 可能です．

実はこのようなことをせずとも，\(f(x)\) の値を \(1\) 回求めるのとほとんど同じ要領で二分探索できます． ペナルティを決め売ったあとのDPで，コスト最小の中で使った部分列の個数最小も求めるようにするとよいです． 詳細は解答例を参考にしてください．

ペナルティの値域は \([0,N]\) を考えれば十分で，一回の DP が \(O(N)\) で行えるため，計算量は全体で \(O(N \log N)\) になります．

解答例