Overview

This problem asks us to minimize the sum of inspection time and travel time when visiting and inspecting all \(N\) shelves arranged in a straight line. Since the total inspection time is fixed, the problem essentially reduces to “minimizing the travel time.”

Analysis

Observation 1: Inspection time is fixed regardless of the order

No matter what order we inspect the shelves, since we must inspect all \(N\) shelves, the total inspection time will always be \(\sum_{i=1}^{N} T_i\). This is not subject to optimization. Therefore, we only need to think about how to minimize the travel time.

Observation 2: We must visit both ends of the shelves

Since we have to inspect all shelves, we naturally need to visit both the leftmost shelf \(1\) and the rightmost shelf \(N\).

From the starting position \(S\): - The distance to the left end (shelf \(1\)) is \(\text{left} = S - 1\) (in terms of the number of shelves). - The distance to the right end (shelf \(N\)) is \(\text{right} = N - S\).

Issues with a Naive Approach

A naive approach like “trying all permutations” would require \(N!\) combinations, which is far too slow for \(N \leq 10^6\). However, by utilizing the structure of moving along a straight line, we can find the answer using a simple formula.

Optimal Movement Strategy

To visit both the left and right ends on a straight line, the two most efficient ways to move are as follows:

1. First go to the left end, change direction, and then go all the way to the right end.
   \(\to\) Travel distance \(= \text{left} + (N-1)\)
2. First go to the right end, change direction, and then go all the way to the left end.
   \(\to\) Travel distance \(= \text{right} + (N-1)\)

In both cases, the idea is to first go to one end and then traverse the entire segment (of length \(N-1\)). Any intermediate shelves can be visited and inspected during this movement, so no detours are necessary.

Since we just need to choose the smaller of the two, the minimum travel distance (in terms of shelves) is:

\[ (N-1) + \min(\text{left}, \text{right}) \]

Thus, it is optimal to head towards the closer end first (which is why we take the \(\min\)).

Algorithm

The answer can be found in \(O(N)\) time with the following steps:

1. Calculate the total inspection time \(\text{sumT} = \sum T_i\).
2. Find the distance to the left end \(\text{left} = S-1\), and the distance to the right end \(\text{right} = N-S\).
3. Calculate the minimum travel distance (in terms of shelves) as \(\text{travel} = (N-1) + \min(\text{left}, \text{right})\).
4. The answer is \(\text{sumT} + D \times \text{travel}\).

Let’s verify this with a concrete example. For \(N=5,\ S=2,\ D=10\), we have \(\text{left}=1\) and \(\text{right}=3\), so it is optimal to go to the left end (shelf 1) first and then head to the right end (shelf 5). The travel distance is \((5-1) + \min(1,3) = 4 + 1 = 5\), making the travel time \(5 \times 10 = 50\) minutes. Adding the total inspection time to this gives the final answer.

Complexity

• Time Complexity: \(O(N)\) (We only need to sum up the values while reading the input)
• Space Complexity: \(O(1)\) (No need to store each \(T_i\); keeping only the sum is sufficient)

Implementation Points

• Beware of overflow: Since there are up to \(10^6\) elements of \(T_i \leq 10^9\), their sum can be around \(10^{15}\). Furthermore, the product of \(D \leq 10^9\) and the travel distance (up to approximately \(1.5 \times 10^6\)) can also be around \(10^{15}\). Since their sum will exceed the range of a 32-bit integer, make sure to use a 64-bit integer type (such as long long in C++).

• Large input size: Since \(N\) can be up to \(10^6\), using fast I/O methods (like scanf or cin.tie(nullptr) in C++) is recommended.

• You only need to add \(T_i\) to the sum, so there is no need to store all elements in an array, which also improves memory efficiency.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N; long long D; long long S;
    scanf("%d %lld %lld", &N, &D, &S);
    long long sumT = 0;
    for(int i=0;i<N;i++){
        long long t;
        scanf("%lld",&t);
        sumT += t;
    }
    long long left = S-1;
    long long right = (long long)N - S;
    long long travel = (long long)(N-1) + min(left, right);
    long long ans = sumT + D * travel;
    printf("%lld\n", ans);
    return 0;
}

---

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