キーエンス プログラミングコンテスト 2021 A Two Sequences 2
$ N \leq 2 * 10^5なので愚直に$ O(N^2)かけて計算しても間に合わない. そこで求める$ c_iを差分更新していくことを考える. 具体的には$ c_iの値は, $ max(c_i, max\{A_j\}(1 \leq j \leq i) * b_i)となる. $ max\{A_j\}の部分はあらかじめ累積maxを$ O(N)かけて前計算しておくことで高速に処理できる. この工夫で計算量は$ O(N)に改善され, この問題が解けた.