Overview

This problem asks us to calculate the sum of forecast errors for each location and find the maximum value among them. It can be solved by straightforwardly calculating according to the definition.

Analysis

In this problem, we need to calculate the sum of forecast errors \(S_i\) over \(D\) days for each of the \(N\) locations, and output the maximum value.

• The forecast temperature for location \(i\) is the same value \(T_i\) every day.
• The forecast error is defined as \(|A_{i,j} - T_i|\) (absolute value).
• For each location, we sum the errors for \(D\) days and find the maximum among all locations.

No special algorithm is required; calculating exactly as defined is sufficient. Since the constraint \(N \times D \leq 10^6\) is guaranteed, the computational complexity is not an issue even if we scan all the data.

Example

For example, if \(N=2, D=3\), the forecast temperatures are \(T = [10, 20]\), and the actual temperatures are: - Location 1: \([12, 8, 15]\) - Location 2: \([25, 18, 20]\)

In this case: - \(S_1 = |12-10| + |8-10| + |15-10| = 2 + 2 + 5 = 9\) - \(S_2 = |25-20| + |18-20| + |20-20| = 5 + 2 + 0 = 7\)

The maximum value is \(\max(9, 7) = 9\).

Algorithm

1. Read \(N\) and \(D\).
2. Read the forecast temperatures \(T_1, T_2, \ldots, T_N\).
3. For each location \(i\):
   • Read the actual temperatures \(A_{i,1}, \ldots, A_{i,D}\).
   • Calculate \(S_i = \sum_{j=1}^{D} |A_{i,j} - T_i|\).
4. Output the maximum value of \(S_1, S_2, \ldots, S_N\).

Complexity

• Time Complexity: \(O(N \times D)\) (calculating the error once for each day at each location)
• Space Complexity: \(O(D)\) (it is sufficient to keep the actual temperatures for only one location at a time)

Since there is a constraint of \(N \times D \leq 10^6\), it runs fast enough.

Implementation Tips

• There is no need to read the temperature data for all locations into memory at once; processing them one by one saves memory. In the code, we can read the data for each location inside the for i in range(N) loop and calculate \(S_i\) immediately.

• By initializing the variable ans to 0 and updating it with max each time we calculate \(S_i\), we can eventually obtain the maximum value. (Since \(S_i \geq 0\) always holds as it is a sum of absolute values, initializing it to 0 is perfectly fine.)

  Source Code

N, D = map(int, input().split())
T = list(map(int, input().split()))
ans = 0
for i in range(N):
    A = list(map(int, input().split()))
    s = sum(abs(a - T[i]) for a in A)
    ans = max(ans, s)
print(ans)

This editorial was generated by claude4.6opus-thinking.