\(t_i = 1\) であるような操作を代入操作、\(t_i = 2\) であるような操作を加算操作と呼ぶことにします。

代入操作を行うと、それまでの操作が一旦リセットされます。そこで、最後に代入操作を行ったのが \(k\) 回目であるとします。\(k\) 回目より前の操作は全て無視せず行うとしてよく、\(k\) 回目より後の代入操作（これが合計 \(n\) 回あるとします）は全て無視しなければなりません。\(n \gt K\) であるとき \(k\) 回目が最後の代入操作となるようにすることはできないので、以降 \(n \leq K\) を仮定します。

上の考察から、\(k\) 回目より後の加算操作を \(0\) 回以上 \(K - n\) 回以下無視することで \(x\) に足される値を最大化するという問題に帰着されます。\(k\) 回目より後の加算操作を \(y_i\) が小さい方から順に見て、\(y_i < 0\) である操作のみ、最大 \(K - n\) 回無視するのが最適です。しかし、全ての \(k\) に対して毎回 \(y_i\) をソートして無視する操作を選んでいては、実行時間制限に間に合いません。

そこで、\(k\) を後ろから順番に試していき、毎回無視する操作を選び直すのではなく、それまでの計算結果を利用できるような方法を考えてみます。無視する加算操作の \(y_i\) からならなる多重集合を \(S\)、それ以外の加算操作の \(y_i\) からなる多重集合を \(T\) とおくと、

• \(|S| \leq K - n\)
• \(\displaystyle \max_{x \in S} x \leq \min_{x \in T} x\)
• \(x \in S \Rightarrow x \lt 0\)
• \(|S| \lt K - n \Rightarrow \min_{x \in T} x \geq 0\)

が全て成り立つならば最大値が達成されます。

また、\(k\) を後ろから試していったときの変化は次の二種類に絞られます。

• ケース 1 : 無視しなければならない代入操作が増える。すなわち、\(n\) が \(1\) 増える。
• ケース 2 : 考慮しなければならない加算操作が増える。

ケース 1 : \(n\) を \(n' = n + 1\) に置き換えるとき、

• \(|S| \lt K - n\) ならば、何もしない。
• \(|S| = K - n\) ならば、\(|S| \gt K - n'\) となってしまうので、\(S\) の最大値を \(S\) から取り除き、\(T\) に追加する。

とすれば、\(n\) を \(n'\) に置き換えた後も前述の条件が満たされます。

ケース 2 : \(y_i = y'\) であるような加算操作を新たに考えるとき、

• \(y' \geq 0\) ならば、\(T\) に \(y'\) を追加する
• \(y' \lt 0\) ならば、\(S\) に \(y'\) を追加する。これによって \(|S| \gt K - n\) となってしまたならば、\(S\) の最大値を \(S\) から取り除き、\(T\) に追加する。

とすれば、\(y'\) を置き換えた後も前述の条件が満たされます。

これらの操作は、全て最大ヒープ・最小ヒープを用いて実装することができます。\(T\) に含まれる要素の総和を常に管理しておくことで、最大値を高速に計算することができます。\(S, T\) の要素数が変化する回数は合計 \(O(N)\) 回であるので、\(O(N \log N)\) の時間計算量でこの問題を解くことができました。

実装の際は、新たに \(t_0 = 1, y_0 = 0\) であるような操作を追加して考えると簡潔になるでしょう。

実装例 (C++) :