Contest Duration: - (local time) (100 minutes) Back to Home

## F - Sum Sum Max Editorial by en_translator

Let $$\displaystyle z_i = \sum_{k = 1}^i y_k$$, where $$z_0 = 0$$.

For $$z_{i - 1} \lt k \leq z_i$$, it always holds that $$C_k = x_i$$. We will use this property to find the maximum value of $$A_{z_{i - 1} + 1}, \dots, A_{z_{i}}$$.
For convenience, let $$A_0 = B_0 = 0$$. Then, for $$1 \leq n \leq z_i - z_{i - 1}$$,

\begin{aligned} B_{z_{i - 1} + n} &= B_{z_{i - 1}} + \sum_{k = 1}^n C_{z_{i - 1} + k} \\ &= B_{z_{i - 1}} + \sum_{k = 1}^n x_i \\ &= B_{z_{i - 1}} + x_i n, \end{aligned}

\begin{aligned} A_{z_{i - 1} + n} &= A_{z_{i - 1}} + \sum_{k = 1}^n B_{z_{i - 1} + k} \\ &= A_{z_{i - 1}} + \sum_{k = 1}^n (B_{z_{i - 1}} + x_i k) \\ &= A_{z_{i - 1}} + B_{z_{i - 1}}n + x_i \times \frac{n(n + 1)}{2}. \end{aligned}

therefore, we can express as $$A_{z_{i - 1} + n} = an^2 + bn + c$$. If we denote the left hand side by $$f(n)$$, the problem is boiled down to the problem of finding the maximum value of $$f(1), \dots, f(z_i - z_{i - 1})$$.

#### [1] If $$a \geq 0$$

Since $$f(n + 1) - f(n) = 2an + a + b$$ is monotonically increasing on $$n$$, there exists an integer $$1 \leq m \leq z_i - z_{i - 1}$$ such that

• $$f(1) \geq \dots \geq f(m)$$,
• $$f(m) \lt \dots \lt f(z_i - z_{i - 1})$$.

Therefore, either $$f(1), f(z_i - z_{i - 1})$$ is the maximum value.

#### [2] If $$a \lt 0$$

Since $$f(n + 1) - f(n) = 2an + a + b$$ is monotonically decreasing on $$n$$, there exists an integer $$1 \leq m \leq z_i - z_{i - 1}$$ such that

• $$f(1) \leq \dots \leq f(m)$$,
• $$f(m) \gt \dots \gt f(z_i - z_{i - 1})$$.

$$f(m)$$ is the maximum value.

We describe how to find $$m$$ fast using ternary search. Let $$g(n) = f(n + 1) - f(n)$$, then $$f(m_2) - f(m_1) = g(m_1) + \dots + g(m_2 - 1)$$, so

• if $$f(m_1) \leq f(m_2)$$, then $$g(m_1) + \dots + g(m_2 - 1) \geq 0$$, and as $$g(n)$$ is monotonically decreasing, we have $$g(m_1) \geq 0$$. Therefore, $$f(m_1) \leq f(m_1 + 1)$$, hence $$m_1 \lt m$$.
• if $$f(m_1) \gt f(m_2)$$, then $$g(m_1) + \dots + g(m_2 - 1) \lt 0$$, and as $$g(n)$$ is monotonically decreasing, we have $$g(m_2 - 1) \lt 0$$. Therefore, $$f(m_2 - 1) \gt f(m_2)$$, hence $$m \lt m_2$$.

In either case, $$l < m < r$$ is preserved.
By choosing $$\displaystyle m_1 = \left\lfloor \frac{l + r}{2} \right\rfloor, m_2 = \left\lfloor \frac{l + r}{2} \right\rfloor + 1$$, the value $$r - l$$ is halved in each step, so $$m$$ can be found in a total complexity of $$O(\log(z_{i} - z_{i - 1}))$$.

Therefore, by finding the maximum value of $$A_{z_{i - 1} + 1}, \dots, A_{z_{i}}$$ in the order of $$i = 1, \dots, N$$, the problem has been solved in a total of $$O(N \log M)$$ time. Here, the values of $$A_{z_{i - 1}}$$ and $$B_{z_{i - 1}}$$ are required, which can be computed from the equations$$A_{z_{i - 1} + n}$$ and $$B_{z_{i - 1} + n}$$ in a constant time.

Sample code (C++)

### Postscript

For functions $$f : \mathbb{Z} \mapsto \mathbb{R}$$ and $$g(n) = f(n + 1) - f(n)$$, if $$g(n)$$ is monotonically increasing, then $$f(n)$$ is said to be concave; if $$g(n9$$ is monotonically decreasing, then $$f(n)$$ is said to be convex. In order to find the extremum of concave/convex function, techniques like ternary search and golden-selection search are frequently used.

posted:
last update: