Official

A - A Multiply Editorial by physics0523

ヒント

Hint 1 ある区間 \(A_l,A_{l+1},\dots,A_r\)に乗算を行った際、 \(\sum A\) ( \(A\) の総和 ) の値を立式してみましょう。

Hint 2 乗算後の \(\sum A\) は \(A_1+A_2+\dots+A_N + (C-1)(A_l+A_{l+1}+\dots+A_r)\) となります。
このうち \(A_1+A_2+\dots+A_N\) は不変です。
\(C\) の値に対して場合分けして、 \((A_l+A_{l+1}+\dots+A_r)\) がどうあるべきか考えてみましょう。

Hint 3 \(C \ge 1\) なるとき \((A_l+A_{l+1}+\dots+A_r)\) を最大化、 \(C<1\) なるとき \((A_l+A_{l+1}+\dots+A_r)\) を最小化すべきです。
いま、問題は \(A_l+A_{l+1}+\dots+A_r\) が 最大/最小 となるような \(l,r\) を選択するというものに帰着されました。ここまで来ればあとは有名問題です。

posted:
last update: