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

## D - Wandering Editorial by evima

Since the constraint states $$N \le 200000$$, the solution of naively simulating the movements of the robot takes $$\Theta(N^2)$$ does not finish in time limit and it will get TLE. Let’s call a sequence of movements “move in the positive direction by $$A_1$$. Move in the positive direction by $$A_2$$. Move in the positive direction by $$A_3$$. $$\ddots$$ Move in the positive direction by $$A_2$$.” as “Movement $$i$$”. Here, for all integer $$i$$ such that $$1 \le i \le N$$, the following values can easily found in a total of $$O(N)$$ time (in the increasing order of $$i$$):

• $$p_i$$ : The overall delta of coordinate performed by movement $$i$$
• $$q_i$$ : The maximum coordinate that robot reaches if it starts movement $$i$$ from coordinate $$0$$

With those values calculated, the answer can also be found as follows:

• Let $$r = 0$$, which stores the answer (maximum coordinate)
• Let $$x = 0$$, which stores the current coordinate, and perform the following operations for each $$i = 1, 2, 3, \dots , N$$:
• Replace $$r$$ with $$\max(r, x + q_i)$$
• Replace $$x$$ with $$x + p_i$$

The total time complexity is $$O(N)$$.

posted:
last update: