Overview

This problem asks us to find the minimum total time (travel time + inspection time) to visit and inspect all \(N\) shelves arranged in a straight line.

Analysis

1. Separation of Inspection Time and Travel Time

In this problem, we need to “inspect all shelves exactly once”. The time \(T_i\) required to inspect shelf \(i\) is always incurred regardless of the order in which we visit the shelves. Therefore, the total inspection time \(\sum_{i=1}^{N} T_i\) is constant, and we only need to minimize the total travel time (= total travel distance \(\times D\)).

2. Minimizing the Travel Distance

The shelves are arranged in a straight line from \(1\) to \(N\). To visit all shelves at least once, we must reach both the leftmost shelf \(1\) and the rightmost shelf \(N\).

Starting from the initial position \(S\), there are essentially only two patterns of travel paths to visit both the leftmost shelf \(1\) and the rightmost shelf \(N\):

• Pattern A: Go to the leftmost end first, then turn back and go to the rightmost end
  • Path: \(S \to 1 \to N\)
  • Travel distance: \((S - 1) + (N - 1)\)
• Pattern B: Go to the rightmost end first, then turn back and go to the leftmost end
  • Path: \(S \to N \to 1\)
  • Travel distance: \((N - S) + (N - 1)\)

It is optimal to choose the path with the shorter travel distance between these two options.

3. Inspecting Shelves on the Way

Although there is a rule that “simply passing through a shelf does not count as inspecting it”, we can inspect each shelf by stopping there during our travel. This allows us to inspect all shelves exactly once without any extra movement (backtracking).

For example, on the way from the initial position \(S\) to the leftmost shelf \(1\), we can stop and inspect each shelf in order. After reaching the leftmost shelf \(1\), we can move towards the rightmost shelf \(N\) while inspecting the remaining shelves (those to the right of \(S\)) in sequence. This completes the inspection of all shelves without any unnecessary backtracking.

Therefore, the minimum travel distance can be expressed as follows: * When \(N = 1\): \(0\) * When \(N > 1\): \(\min(S - 1, N - S) + (N - 1)\)

Algorithm

1. Calculate the sum of the input inspection times \(T_i\), denoted as sum_T.
2. Calculate the distance from the starting position \(S\) to the leftmost end, left_dist \(= S - 1\), and the distance to the rightmost end, right_dist \(= N - S\).
3. Find the minimum travel distance min_dist as \(\min(\text{left\_dist}, \text{right\_dist}) + (N - 1)\) (except when \(N=1\), where it is \(0\)).
4. The required minimum total time is sum_T + min_dist * D.

Complexity

• Time Complexity: \(O(N)\) We need to scan the input \(N\) times to calculate the sum of \(T_i\). Since the other calculations can be done in \(O(1)\), the overall algorithm runs in \(O(N)\) time, which is well within the time limit.
• Space Complexity: \(O(1)\) Since we can add each input \(T_i\) to the running sum on the fly, we do not need to store them in an array. Therefore, the additional memory required is constant.

Key Implementation Details

• Preventing Overflow: Since the values of \(N, D,\) and \(T_i\) can be large, the total time may reach around \(10^{18}\). In C++, you must perform calculations using a 64-bit integer type like long long instead of the standard int type (which has a maximum value of about \(2 \times 10^9\)).

• Handling Corner Cases: When \(N = 1\), no travel is required. Use conditional branching to ensure the travel distance is \(0\).

  Source Code

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    int 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 min_dist = 0;
    if (N > 1) {
        long long left_dist = S - 1;
        long long right_dist = N - S;
        min_dist = min(left_dist, right_dist) + (N - 1);
    } else {
        min_dist = 0;
    }

    long long ans = sum_T + min_dist * D;
    cout << ans << "\n";

    return 0;
}

---

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