Overview

We want to find the minimum total time required to inspect all shelves exactly once.
Since the total inspection time is constant regardless of the order, we only need to minimize the “travel time”.

Observation

First, since every shelf must be inspected exactly once, the sum of the inspection times \(T_i\) is always constant,

\(T_1 + T_2 + \cdots + T_N\)

regardless of the order in which we visit them.

Therefore, this problem can be rephrased as follows:

Find the minimum travel distance to visit all shelves from shelf \(1\) to shelf \(N\), starting from shelf \(S\).

Since the shelves are arranged in a straight line, to visit all shelves, we must eventually cover the entire interval \([1, N]\).

The distance from shelf \(1\) to shelf \(N\) is

\((N - 1) \times D\)

When the starting position is shelf \(S\), the shortest route to visit all shelves is one of the following two:

1. Go to shelf \(1\) first, then proceed to shelf \(N\).
2. Go to shelf \(N\) first, then proceed to shelf \(1\).

The respective travel distances are as follows:

• When going to shelf \(1\) first:
  Travel distance equivalent to \((S - 1) + (N - 1)\) shelves.
• When going to shelf \(N\) first:
  Travel distance equivalent to \((N - S) + (N - 1)\) shelves.

Therefore, the minimum travel distance is

\(((N - 1) + \min(S - 1, N - S)) \times D\)

For example, consider the case where \(N = 5, S = 2\).

• Going to shelf \(1\) first: \(2 \to 1 \to 5\)
  The number of shelves traveled is \(1 + 4 = 5\).
• Going to shelf \(5\) first: \(2 \to 5 \to 1\)
  The number of shelves traveled is \(3 + 4 = 7\).

Therefore, the minimum number of shelves traveled is \(5\).

A naive search of all inspection orders would check \(N!\) permutations, which is far too slow for \(N \leq 10^6\). However, by noticing that traveling from one end to the other is mandatory to visit all shelves on a straight line, we can find the answer using the formula above.

Algorithm

1. Read all \(T_i\) and calculate the total inspection time total.
2. Calculate the minimum travel time using the following formula:

\(move = ((N - 1) + \min(S - 1, N - S)) \times D\)

1. The answer is

\(total + move\)

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\)

Implementation Points

\(N, D,\) and \(T_i\) can be large, and the total time can be around \(10^{15}\). Therefore, you need to use long long instead of int.

Also, since we only need the sum of \(T_i\), there is no need to store them in an array. It is sufficient to add each \(T_i\) to total as you read it.

Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, D, S;
    cin >> N >> D >> S;

    long long total = 0;
    for (int i = 0; i < N; i++) {
        long long T;
        cin >> T;
        total += T;
    }

    long long move = ((N - 1) + min(S - 1, N - S)) * D;
    cout << total + move << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.