Official

A - A Multiply Editorial by evima

Hints

Hint 1 When multiplying a certain range \(A_l,A_{l+1},\dots,A_r\), let’s formulate the value of \(\sum A\) (the total sum of \(A\)).

Hint 2 After multiplication, \(\sum A\) becomes \(A_1+A_2+\dots+A_N + (C-1)(A_l+A_{l+1}+\dots+A_r)\).
Among these, \(A_1+A_2+\dots+A_N\) remains unchanged.
Depending on the value of \(C\), consider how \((A_l+A_{l+1}+\dots+A_r)\) should be.

Hint 3 When \(C \ge 1\), \((A_l+A_{l+1}+\dots+A_r)\) should be maximized, and when \(C<1\), \((A_l+A_{l+1}+\dots+A_r)\) should be minimized.
Now, the problem is reduced to selecting \(l,r\) such that \(A_l+A_{l+1}+\dots+A_r\) is maximized/minimized. If you’ve come this far, the rest is a well-known problem.

posted:
last update: