Overview

A letter addressed to location \(i\) must pass through exactly \(i-1\) edges. Therefore, the minimum fatigue level can be found by summing up “the number of letters \(\times\) the distance from the post office” for each location.

Analysis

Consider a single letter addressed to location \(i\).

To deliver this letter, the following \(i-1\) movements must be made on the outbound trip:

• From location \(1\) to location \(2\)
• From location \(2\) to location \(3\)
• \(\ldots\)
• From location \(i-1\) to location \(i\)

During these movements, the letter has not been delivered yet and remains in hand. Therefore, each movement increases the fatigue level by \(1\), inevitably contributing a total of \(i-1\) to the fatigue level.

Thus, if there are \(B_i\) letters to be delivered to location \(i\), the fatigue level they generate is at least

\[ (i-1)B_i \]

This lower bound can actually be achieved. For example, we can carry all the letters at once to the farthest destination, delivering the letters for each location when we arrive there. Each letter is carried only up to its destination and no further.

Therefore, the answer is

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

For example, in the case of \(B_2=2,\ B_3=1,\ B_4=0,\ B_5=3\), the fatigue level is:

\[ 1 \times 2 + 2 \times 1 + 3 \times 0 + 4 \times 3 = 16 \]

An approach that enumerates how to divide the delivery routes will result in TLE (Time Limit Exceeded) due to the extremely large number of candidates. Furthermore, while it might seem that carrying letters together reduces the fatigue level, the fatigue level is proportional to the number of letters, so carrying them together does not change the fatigue level generated by each letter. There is no need to consider combinations of routes.

Algorithm

1. Iterate through location \(2\) to location \(N\) in order.
2. For each location \(i\), multiply its distance from the post office \(i-1\) by the number of letters \(B_i\).
3. Sum these values up and output the total.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\) auxiliary space.
  However, since the implementation reads the entire input at once, it is \(O(N)\) including the input buffer.

Implementation Notes

The first number of letters in the input is \(B_2\) for location \(2\). Since its distance is \(1\), we can assign the distance starting from \(1\) using enumerate(it, 1).

Also, note that the answer can be very large. Since Python integers do not overflow like fixed-width integers, you can calculate it as-is.

Source Code

import sys

it = map(int, sys.stdin.buffer.read().split())
next(it)
answer = sum(distance * letters for distance, letters in enumerate(it, 1))
print(answer)

---

This editorial was generated by gpt-5.6-sol-high.