Summary

This problem asks us to find the minimum total “travel time + inspection time” to inspect all \(N\) shelves arranged in a straight line. Since the total inspection time is constant, this is essentially a problem of minimizing the travel time.

Analysis

Inspection Time is Constant

First, an important observation is that since we inspect every shelf exactly once, the total inspection time \(\sum_{i=1}^{N} T_i\) is always constant regardless of the order of inspections. Therefore, we only need to minimize the travel time.

Minimizing Travel Time = Visiting All Points on a Line

Since the shelves are arranged in order along a straight line, this reduces to the problem of finding the “shortest path starting from point \(S\) on a number line that visits all points from \(1\) to \(N\)”.

To visit all shelves, we must visit both the leftmost shelf \(1\) and the rightmost shelf \(N\). Once these two endpoints are covered, all shelves in between will have been passed through (passing through is not enough for inspection, but we can simply stop and inspect them along the way).

Optimal Movement Strategy

There are essentially two ways to visit both endpoints \(1\) and \(N\) starting from the starting point \(S\):

1. Go to the leftmost shelf \(1\) first, then head to the rightmost shelf \(N\)
   • Travel distance (in terms of shelves): \((S-1) + (N-1)\)
2. Go to the rightmost shelf \(N\) first, then head to the leftmost shelf \(1\)
   • Travel distance (in terms of shelves): \((N-S) + (N-1)\)

In both cases, we traverse the entire width \((N-1)\) fully once, and in addition, we make one extra round trip to the closer endpoint.

Therefore, the minimum travel distance (in units of shelves) is as follows:

\[ (N-1) + \min(S-1,\ N-S) \]

Here, \(S-1\) is the number of shelves to the left, and \(N-S\) is the number of shelves to the right. It is optimal to handle the closer endpoint first.

Concrete Example

Consider the case where \(N=5,\ S=3\). There are \(S-1=2\) shelves on the left and \(N-S=2\) shelves on the right. - Going to the left endpoint \(1\) first: \(3 \to 1\) (distance 2) \(\to 1 \to 5\) (distance 4) = total 6 - Going to the right endpoint \(5\) first: \(3 \to 5\) (distance 2) \(\to 5 \to 1\) (distance 4) = total 6

Using the formula: \((5-1) + \min(2,2) = 4 + 2 = 6\), which matches.

The final answer is this travel distance multiplied by \(D\), plus the total inspection time.

\[ \text{Answer} = \sum_{i=1}^{N} T_i + D \times \left( (N-1) + \min(S-1,\ N-S) \right) \]

Algorithm

1. Calculate the total inspection time \(\text{total} = \sum_{i=1}^{N} T_i\).
2. When \(N = 1\), no movement is required, so the answer is simply \(\text{total}\).
3. Otherwise, choose the smaller of the number of shelves on the left \(S-1\) and on the right \(N-S\), and let the travel distance be \((N-1) + \min(S-1, N-S)\).
4. Output \(\text{total} + D \times (\text{travel distance})\).

The key point of this problem is that it can be calculated directly using a closed-form expression (formula), without the need for any special search or dynamic programming.

Complexity

• Time Complexity: \(O(N)\) (dominated by reading the input to find the sum of inspection times)
• Space Complexity: \(O(N)\) (to store the input data; actually, it can be optimized to \(O(1)\) by reading sequentially)

Implementation Points

• Since the input size is large (\(N \leq 10^6\)), we use sys.stdin.buffer.read() in Python to read everything at once for fast processing. Reading line-by-line using input() might be too slow.

• Since \(T_i\) and \(D\) can be up to \(10^9\) and \(N\) is also large, the total value can be extremely large. However, Python automatically handles arbitrarily large integers, so we do not need to worry about overflow (note that in languages like C++, you will need long long or equivalent).

• Although it might seem that no conditional branching is necessary because \(\min(S-1, N-S)\) and \((N-1)\) naturally become \(0\) when \(N = 1\), the code explicitly handles this case for safety.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); d = int(data[1]); s = int(data[2])
    total = 0
    for i in range(n):
        total += int(data[3 + i])
    if n == 1:
        print(total)
        return
    left = s - 1
    right = n - s
    travel = (n - 1) + min(left, right)
    print(total + d * travel)

main()

---

This editorial was generated by claude4.8opus-high.