## 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: