Overview

This is a problem where you select 1 truck out of \(N\) trucks and minimize the total fuel consumption when visiting all \(M\) delivery destinations in order.

Analysis

First, let’s express the total fuel consumption when a specific truck \(i\) is selected as a formula. Let \(E_i\) be the fuel efficiency coefficient of truck \(i\), and \(C_1, C_2, \ldots, C_M\) be the distances to each delivery destination. The total fuel consumption is as follows:

\[(E_i \times C_1) + (E_i \times C_2) + \dots + (E_i \times C_M)\]

This expression can be factored by the common factor \(E_i\) (distributive law):

\[E_i \times (C_1 + C_2 + \dots + C_M)\]

Here, the part \((C_1 + C_2 + \dots + C_M)\) is a constant value (the total distance of the delivery route) that does not change regardless of which truck is selected. If we denote this as \(S\), the total fuel consumption can be expressed in the very simple form \(E_i \times S\).

Since \(S\) is a positive value, to minimize \(E_i \times S\), we can see that we should select the truck with the smallest fuel efficiency coefficient \(E_i\).

Why a naive calculation won’t work

If we use a double loop that “calculates and sums up the fuel consumption for all delivery destinations (\(M\) locations) for every truck (\(N\) trucks),” the computational complexity becomes \(O(N \times M)\). In this problem, \(N, M \leq 10^5\), so a maximum of about \(10^{10}\) calculations would be needed, which will not finish within the time limit. It is essential to significantly reduce the computational complexity through the mathematical transformation described above.

Algorithm

1. Calculate the total distance to delivery destinations \(S = \sum_{j=1}^{M} C_j\).
2. Find the minimum fuel efficiency coefficient \(E_{min} = \min(E_1, E_2, \ldots, E_N)\).
3. Calculate and output \(E_{min} \times S\).

Complexity

• Time complexity: \(O(N + M)\)
  • Finding the minimum among trucks takes \(O(N)\), and computing the sum of delivery distances takes \(O(M)\).
• Space complexity: \(O(N + M)\)
  • If input values are stored in lists or similar structures, memory proportional to the number of elements is required.

Implementation Notes

• Fast input: Since \(N, M\) can be as large as \(10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Sum and minimum: By using standard built-in functions such as sum() and min(), the processing can be done concisely and efficiently.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # この手法は、N, M が 10^5 程度の規模であれば Python で高速に動作します
    data = sys.stdin.read().split()
    
    if not data:
        return
    
    # トラックの数 N と配送先の数 M を取得
    n = int(data[0])
    m = int(data[1])
    
    # トラック i が全配送先を巡回する際の合計燃料消費量は、
    # Σ (E_i * C_j) = E_i * Σ C_j と計算できる。
    # これを最小化するためには、燃費係数 E_i が最小のトラックを選択すればよい。
    
    # トラックの燃費係数 E_i のリストから最小値を取得
    # E_i はリストの 2 番目から n 個分
    min_e = min(map(int, data[2 : n + 2]))
    
    # 配送先へのルート距離 C_j の合計を計算
    # C_j はリストの n + 2 番目から m 個分
    sum_c = sum(map(int, data[n + 2 : n + m + 2]))
    
    # 最小の燃料消費量を出力
    print(min_e * sum_c)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-preview.