ABC240 F - Sum Sum Max (500)
愚直に計算すると各テストケースで$ \mathcal{O}(M)かかってしまう
Aが最大値になる可能性のある点について考察すると、Bが非負から負になる直前であることが分かる
$ A_i = A_{i-1} + B_i \ge A_{i-1}だし、$ A_{i+1} = A_i + B_{i+1} \lt A_i
$ N個の最大値候補を見つけてその中の最大値を返却する
最大値の初期値は最初の数字にしておく
1個は選ぶ必要があるため、全て負だとしても0にはできない
以前のA,Bを覚えておく
$ A_{prev}, B_{prev}とすると、次の数字$ X_iを$ j個使ったときの値$ A_{now}は$ A_{now} = A_{prev} + jB_{prev} + \frac{j (j+1) X_i}{2}
それぞれ$ N個で以下を行う
$ B_{y_i} \ge 0なら最後まで使えるので、最後まで使って$ A_{now}を求めて最大値を比較、更新
そうでない場合、$ Bが負になる直前の位置を二分探索で求めて最大値を比較、更新
それぞれ二分探索する可能性があるので$ \mathcal{O}(N \log M)