Overview

This problem asks us to find the minimum total time required to visit all \(N\) shelves lined up in a straight line and complete the inspection of the packages. Since the total time taken for inspection does not change regardless of how we move, the problem essentially reduces to finding the minimum travel distance to visit all shelves starting from the initial position \(S\).

Analysis

1. Decomposing the Total Time

The total work time can be divided into two parts: the “total travel time” and the “total inspection time”. $\(\text{Total Time} = \text{Total Travel Time} + \text{Total Inspection Time}\)$

Since we must inspect every shelf exactly once, the total inspection time is always the sum of the inspection times \(T_i\) of each shelf, regardless of the order in which we visit them. $\(\text{Total Inspection Time} = \sum_{i=1}^{N} T_i\)$ Therefore, we only need to focus on minimizing the “total travel time”.

2. Approach for Minimum Travel Distance

The shelves are lined up in a straight line from \(1\) to \(N\). To visit all shelves, we must visit both the leftmost shelf \(1\) and the rightmost shelf \(N\).

Starting from the initial position \(S\), the shortest path to visit all shelves (including both ends) will always be one of the following two patterns:

• Pattern A (Going to the leftmost shelf first)

  1. From the initial position \(S\), move straight to the leftmost shelf \(1\).
  2. Turn back at shelf \(1\), and move straight to the rightmost shelf \(N\).
  • The travel distance in this case is: $\((S - 1) + (N - 1)\)$

• Pattern B (Going to the rightmost shelf first)

  1. From the initial position \(S\), move straight to the rightmost shelf \(N\).
  2. Turn back at shelf \(N\), and move straight to the leftmost shelf \(1\).
  • The travel distance in this case is: $\((N - S) + (N - 1)\)$

Any other shelves in between (shelves between \(1\) and \(N\)) will inevitably be passed during this round-trip. By stopping to inspect them as we pass by, we can complete the inspection of all shelves without incurring any additional travel distance.

Therefore, the minimum travel distance is the smaller of Pattern A and Pattern B. $\(\text{Minimum Travel Distance} = \min(S - 1, N - S) + (N - 1)\)$

Concrete Example (for \(N = 5, S = 2\))

• Pattern A (Leftmost first): Move \(2 \to 1 \to 5\).
  • The distance is \(|2 - 1| + |1 - 5| = 1 + 4 = 5\).
• Pattern B (Rightmost first): Move \(2 \to 5 \to 1\).
  • The distance is \(|2 - 5| + |5 - 1| = 3 + 4 = 7\).
• The minimum travel distance is \(\min(1, 3) + 4 = 5\), making Pattern A optimal. During this movement, we also pass through shelves \(3\) and \(4\), so inspecting them on the way requires no extra distance.

Algorithm

1. Read \(N, D, S\) and the inspection times \(T_1, T_2, \ldots, T_N\) of each shelf from the input.
2. Calculate the total inspection time \(\sum T_i\).
3. Calculate the minimum travel time using the formula \(\min(S - 1, N - S) \times D + (N - 1) \times D\).
4. Output the sum of the “minimum travel time” and the “total inspection time” as the final answer.

Complexity

• Time Complexity: \(O(N)\) Calculating the sum of the inspection times \(T_i\) takes \(O(N)\) time. Since calculating the travel time can be done in \(O(1)\), the overall time complexity is \(O(N)\), which is fast enough to run well within the time limit even for \(N \le 10^6\).
• Space Complexity: \(O(N)\) Using \(O(N)\) memory to store the input as a list.

Implementation Points

• Fast I/O: In Python, since the number of input elements can be very large (when \(N = 10^6\), there are \(10^6\) values of \(T_i\)), instead of repeatedly calling input(), you can significantly reduce the execution time by reading all inputs at once using sys.stdin.read().split().

• No Overflow Concerns: The answer can be as large as approximately \(10^{15}\). However, since Python natively supports arbitrary-precision integers (integers with no size limit), you do not need to worry about integer overflow.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    D = int(data[1])
    S = int(data[2])

    # T_i の合計を高速に計算
    sum_T = sum(map(int, data[3:]))

    # 1次元上のすべての点を訪問する最短移動距離は、
    # S -> 1 -> N の順（最後に右端Nに到達）か、
    # S -> N -> 1 の順（最後に左端1に到達）のいずれかになります。
    # したがって、最小移動距離は min(S - 1, N - S) * D + (N - 1) * D となります。
    min_move = min(S - 1, N - S) * D + (N - 1) * D

    ans = min_move + sum_T
    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.