キーエンス プログラミング コンテスト2021 A - Two Sequences 2 (300)
愚直に計算すると$ c_iを求めるのに$ O(N^2)かかるので全体で$ O(N^3)になってしまう
$ c_{i-1} を求めるときに候補になった数は$ c_i を求めるときにも候補になり、新しく増える候補は$ a_0b_i, a_1b_i, \cdots , a_ib_i なので$ c_i = \max(c_{i-1}, \max(a) b_i) になる
つまり前回の値と、そこまでの$ aの最大値を持っておけば$ O(1)で計算できるようになる
全体では$ O(N)