Overview

Every letter delivered to location \(i\) must be transported from the post office (location \(1\)) to location \(i\), which always incurs a fatigue level equal to the travel distance of \(i-1\) per letter. Therefore, the answer is \(\sum_{i=2}^{N} (i-1) \times B_i\).

Analysis

Key Observation

First, let’s carefully review the definition of “fatigue level”. When moving from location \(p\) to \(p+1\) on the outbound journey, fatigue is incurred by the number of letters currently in hand at that moment.

Here, let’s focus on a single letter. A single letter addressed to location \(i\) remains in hand the entire time it is transported from the post office (location \(1\)) to location \(i\). In other words, this letter is: - Movement from location \(1 \to 2\) - Movement from location \(2 \to 3\) - \(\ldots\) - Movement from location \((i-1) \to i\)

present in hand during all of these \(i-1\) movements, and contributes \(+1\) to the fatigue level for each movement.

In other words, a single letter addressed to location \(i\) will always incur a fatigue level of \(i-1\), regardless of how it is carried.

Route Configurations Do Not Matter

Although there is flexibility, such as “splitting letters addressed to the same location into multiple trips” or “carrying letters for multiple locations at once,” this actually has absolutely no effect on the total fatigue level.

This because, if we break down the total fatigue level “per letter”, the fatigue contributed by each letter does not depend on the delivery method; it is fixed to “the number of edges the letter crosses = the distance to its destination”. Even if multiple letters are carried simultaneously, the fatigue is simply the sum of the contributions of each individual letter (carrying \(k\) letters in a single movement incurs \(k\) fatigue, which is the sum of \(k\) individual contributions of \(1\) fatigue per letter).

Therefore, the total fatigue level remains the same regardless of the route configuration, and is uniquely determined as:

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

There is no need to devise any clever strategy to find the minimum value.

Example

For example, when \(N=4\), \(B_2=2, B_3=1, B_4=3\): - Addressed to location \(2\): \(2\) letters \(\times\) distance \(1\) = \(2\) - Addressed to location \(3\): \(1\) letter \(\times\) distance \(2\) = \(2\) - Addressed to location \(4\): \(3\) letters \(\times\) distance \(3\) = \(9\)

The total is \(2 + 2 + 9 = 13\), which is the answer.

Algorithm

Simply calculate the above formula.

1. Read \(N\) and \(B_2, \ldots, B_N\).
2. Accumulate \((i-1) \times B_i\) for each \(i\).
3. Output the total.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\) (no extra array is needed if the input is processed on the fly)

Implementation Notes

• Beware of overflow: Since \(N \leq 10^6\) and \(B_i \leq 10^7\), \((i-1) \times B_i\) can be up to approximately \(10^6 \times 10^7 = 10^{13}\). Summing this over \(N\) elements might seem to approach up to \(10^{19}\), but the constraints guarantee that the answer fits within a signed 64-bit integer (up to approximately \(9.2 \times 10^{18}\)). In any case, it will certainly overflow a standard int, so make sure to use long long in C++.

• Fast I/O: Since \(N\) can be as large as \(10^6\), using raw cin might be too slow. In the sample code, fast I/O is achieved using buffer reading with fread and a custom integer parser. Using scanf or ios::sync_with_stdio(false) is often fast enough to pass.

• The core of this problem is to realize that the complex settings described in the problem statement—such as temporarily storing letters or split deliveries—do not affect the final answer.

  Source Code

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

int main(){
    // 高速入力
    static char buf[1 << 25];
    int len = fread(buf, 1, sizeof(buf), stdin);
    int pos = 0;
    auto readInt = [&]() -> long long {
        while (pos < len && (buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') pos++;
        bool neg = false;
        if (pos < len && buf[pos] == '-') { neg = true; pos++; }
        long long x = 0;
        while (pos < len && buf[pos] >= '0' && buf[pos] <= '9') {
            x = x * 10 + (buf[pos] - '0');
            pos++;
        }
        return neg ? -x : x;
    };

    long long N = readInt();
    long long ans = 0;
    for (long long i = 2; i <= N; i++) {
        long long b = readInt();
        ans += (i - 1) * b;
    }
    printf("%lld\n", ans);
    return 0;
}

---

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