Overview

This problem asks us to select one truck from \(N\) trucks and minimize the fuel consumption when visiting all \(M\) delivery destinations. The answer can be found by selecting the truck with the minimum fuel efficiency coefficient and multiplying it by the sum of distances to all delivery destinations.

Analysis

Key Insight

Let’s consider the total fuel consumption when truck \(i\) is selected.

The fuel consumption when truck \(i\) visits all delivery destinations is: $\(E_i \times C_1 + E_i \times C_2 + \cdots + E_i \times C_M\)$

This can be factored by \(E_i\): $\(E_i \times (C_1 + C_2 + \cdots + C_M) = E_i \times \sum_{j=1}^{M} C_j\)$

Verification with a Concrete Example

For example, with \(N = 2, M = 3\), \(E = [3, 2]\), and \(C = [10, 20, 30]\): - Choosing truck 1: \(3 \times 10 + 3 \times 20 + 3 \times 30 = 3 \times 60 = 180\) - Choosing truck 2: \(2 \times 10 + 2 \times 20 + 2 \times 30 = 2 \times 60 = 120\)

Regardless of which truck is chosen, the sum of distances \(\sum C_j = 60\) remains the same.

Optimal Choice

To minimize the total fuel consumption \(E_i \times \sum C_j\), since \(\sum C_j\) is fixed, we can see that we should choose the truck with the minimum \(E_i\).

Comparison with the Naive Approach

The naive approach of “calculating and summing the fuel consumption for each delivery destination for each truck” takes \(O(N \times M)\) time. When \(N, M\) are at most \(10^5\), this results in \(10^{10}\) calculations, risking TLE.

However, based on the analysis above, we only need to find the minimum of \(E_i\) and the sum of \(C_j\), allowing us to solve the problem efficiently.

Algorithm

1. Find the minimum value \(\min(E)\) from array \(E\)
2. Find the sum \(\sum C\) of array \(C\)
3. Output \(\min(E) \times \sum C\)

Complexity

• Time complexity: \(O(N + M)\)
  • Finding the minimum of \(E\) takes \(O(N)\)
  • Finding the sum of \(C\) takes \(O(M)\)
• Space complexity: \(O(N + M)\)
  • Required to store the input

Implementation Notes

• In Python, you can implement this concisely using the min() and sum() functions

• Based on the constraints, the maximum answer could be around \(10^4 \times 10^4 \times 10^5 = 10^{13}\), but since Python doesn’t have integer overflow issues, we can calculate it directly

  Source Code

N, M = map(int, input().split())
E = list(map(int, input().split()))
C = list(map(int, input().split()))

min_E = min(E)
sum_C = sum(C)

print(min_E * sum_C)

---

This editorial was generated by claude4.5opus.