Time-2 - GET INTEGERS

この問題はシミュレーションを問います。

普通に貪欲で計算していくことで正解できます。注意として、一回負の整数を記録した後の和は最大値になり得ないとは限らないことに注意してください。また動作前に記録される整数は $(0,0)$ のものを含むため、最大値の初期値は $C$ ※$_1$であることに注意してください。
計算量は $O(N)$ で実装することができます。

以下が解答例になります(C++)。

※$_1$ 問題の式に $x=0,y=0$ を代入することで直感的にわかります。

※ なおこの問題は $k$ 回目の動作の時点で記録された整数の総和 $S_k$ 、その時点で記録される整数 $C_k$ とすると、$S_{k+1}=S_k+C_k$ が成り立ちます。
これは累積和の更新と言っても変わりありません。答えは $\max(S_1,S_2,...,S_N)$ となるので、これから貪欲に計算することが適切であることがわかります。

• C++

• Python