Overview

This problem asks us to find the minimum total time (the sum of travel time and inspection time) to inspect \(N\) shelves arranged in a straight line, starting from an initial position \(S\) and visiting each shelf exactly once.

Analysis

First, the total inspection time is always \(\sum_{i=1}^N T_i\) regardless of the order in which we inspect the shelves. Therefore, the core of this problem is to “minimize the total travel time.”

Let’s consider the path to minimize travel time. Since the shelves are arranged in a straight line, we must reach both the leftmost shelf (shelf \(1\)) and the rightmost shelf (shelf \(N\)) in order to visit all shelves.

The shortest path starting from position \(S\) that visits all shelves at least once will always fall into one of the following two patterns: 1. Go to the left end, then to the right end: Move from shelf \(S\) to the left end (shelf \(1\)), and then move all the way to the right end (shelf \(N\)). The travel distance in this case is \((S - 1) + (N - 1)\). 2. Go to the right end, then to the left end: Move from shelf \(S\) to the right end (shelf \(N\)), and then move all the way to the left end (shelf \(1\)). The travel distance in this case is \((N - S) + (N - 1)\).

The reason why we only need to consider these two patterns is that any shelves passed along the way can be inspected during the movement, so there is no need for redundant backtracking. For example, in Pattern 1, we can inspect all shelves on the way from \(S\) to \(1\), and then inspect the remaining uninspected shelves on the way from \(1\) to \(N\). This allows us to cover all shelves with a total distance of \((S - 1) + (N - 1)\).

A naive approach of trying all possible visiting orders would take \(O(N!)\) time and result in a TLE (Time Limit Exceeded). However, by taking advantage of the properties of a straight line, we can find the minimum travel distance in \(O(1)\) time.

Finally, we can obtain the answer by multiplying the minimum travel distance by \(D\) and adding it to the total inspection time. Note that since \(N, D, T_i\) can be up to \(10^9\), the maximum possible answer is approximately \(10^6 \times 10^9 \times 2 \approx 2 \times 10^{15}\). Therefore, we must be careful as the answer may exceed the range of a 32-bit signed integer.

Algorithm

1. Read all inspection times \(T_i\) and calculate their sum \(\text{sum\_T}\).
2. Calculate the travel distance for going to the left end first: \(\text{move1} = (S - 1) + (N - 1)\).
3. Calculate the travel distance for going to the right end first: \(\text{move2} = (N - S) + (N - 1)\).
4. Multiply the minimum of \(\text{move1}\) and \(\text{move2}\) by \(D\) to get the minimum travel time \(\text{min\_move}\).
5. Output the answer: \(\text{sum\_T} + \text{min\_move}\).

Complexity

• Time Complexity: \(O(N)\) (the time required to read \(T_i\) and calculate their sum)
• Space Complexity: \(O(1)\) (only constant space is used because we can sum up \(T_i\) on the fly without storing them in an array)

Implementation Points

• Since \(N, D, T_i\) can be large, we must use a 64-bit integer type (long long in C++) to perform intermediate calculations and store the final answer.

• There is no need to store \(T_i\) in an array. We can keep the memory usage minimal by adding each input value directly to the sum as we read it.

  Source Code

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N, D, S;
    if (!(cin >> N >> D >> S)) return 0;
    
    long long sum_T = 0;
    for (int i = 0; i < N; ++i) {
        long long t;
        cin >> t;
        sum_T += t;
    }
    
    long long move1 = S + N - 2;
    long long move2 = 2 * N - S - 1;
    long long min_move = min(move1, move2) * D;
    
    long long ans = sum_T + min_move;
    cout << ans << "\n";
    
    return 0;
}

This editorial was generated by or-glm5.2-high.