Overview

Letters to be delivered to location \(i\) must be kept on hand the entire time they are carried from the post office (location \(1\)) to location \(i\), and fatigue is accumulated proportional to that distance. The answer is the sum of “number of letters \(\times\) distance from the post office” over all letters.

Observation

First, let us analyze how fatigue is accumulated. When moving from location \(p\) to location \(p+1\) on the outbound journey, fatigue is accumulated by an amount equal to the number of letters currently held in hand.

Here, let’s focus on a single letter. To deliver a letter addressed to location \(i\), it must be carried in hand from the post office (location \(1\)) to location \(i\). The edges traversed during this journey are

\[1 \to 2,\quad 2 \to 3,\quad \ldots,\quad (i-1) \to i\]

which are \(i-1\) edges in total. Since this letter is counted as “held in hand” during all of these moves, it always generates exactly \(i-1\) fatigue per letter. This is equal to the distance \(i-1\) from location \(1\) to location \(i\).

The crucial point is that this fatigue cannot be reduced, no matter how we optimize the delivery route. To deliver the letters, we have no choice but to carry them to their destinations, and there is no way to avoid fatigue along the way. Furthermore, since no fatigue is accumulated on the return trips, we do not suffer any penalty as long as we do not make unnecessary extra moves.

Therefore, whether we deliver the letters in multiple trips or all at once, the total fatigue remains the same. The fatigue generated by the \(B_i\) letters addressed to location \(i\) is always

\[B_i \times (i-1)\]

and the overall minimum is given by

\[\sum_{i=2}^{N} B_i \times (i-1)\]

.

One might be tempted to naively search for the optimal route or decide which letters to carry on which trip. However, based on the observation above, how the routes are constructed does not affect the answer, so a simple summation is sufficient.

Let’s verify this with a concrete example. In the case of \(N=3\), \(B_2=2\), \(B_3=3\): - Letters addressed to location \(2\) are carried over a distance of \(1\), so \(2 \times 1 = 2\) - Letters addressed to location \(3\) are carried over a distance of \(2\), so \(3 \times 2 = 6\) - Total: \(8\)

Algorithm

For each location \(i\) (\(2 \leq i \leq N\)), we simply sum the values of \(B_i\) multiplied by the distance \((i-1)\).

The input array data[1..n-1] corresponds to \(B_2, B_3, \ldots, B_N\). Since the \(j\)-th element (\(j=0,1,\ldots\)) is addressed to location \(2+j\), its distance is \((2+j)-1 = j+1\). Therefore, we calculate:

\[\text{ans} = \sum_{j=0}^{N-2} (j+1) \times B_{2+j}\]

Complexity

• Time Complexity: \(O(N)\) (requires only a single pass over the array)
• Space Complexity: \(O(N)\) (to store the input)

Implementation Points

• Since \(N\) can be up to \(10^6\), \(B_i\) up to \(10^7\), and the distance up to \(10^6\), the total sum can exceed the range of a 32-bit integer. In languages like C++, you must use 64-bit integers (long long). In Python, integers automatically support arbitrary precision, so you do not need to worry about overflow.

• Since \(N\) can be large, it is safer to perform fast I/O. In this code, we read the entire input at once using sys.stdin.buffer.read() before processing.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    ans = 0
    # data[1..n-1] が B_2..B_N（計 n-1 個）
    # 地点 2+j (j=0..) までの距離は j+1
    for j in range(n - 1):
        ans += (j + 1) * int(data[1 + j])
    sys.stdout.write(str(ans) + "\n")

main()

---

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