Summary

This problem asks us to find the sum of the absolute differences \(S_i\) between the forecasted temperature \(T_i\) and the actual temperatures \(A_{i,j}\) over \(D\) days for each location, and output the maximum value among them.

Analysis

As described in the problem statement, the total forecast error for location \(i\) is:

\(S_i = \sum_{j=1}^{D} |A_{i,j} - T_i|\)

Therefore, we can perform the following process for each location:

1. Check the forecasted temperature \(T_i\) for location \(i\).
2. Read the actual temperatures for \(D\) days at that location.
3. Sum up \(|A_{i,j} - T_i|\) for each day.
4. Update the maximum value found so far.

For example, if the forecasted temperature at a certain location is \(T_i = 20\) and the actual temperatures are \(18, 23, 20\), the calculation is:

\(|18 - 20| + |23 - 20| + |20 - 20| = 2 + 3 + 0 = 5\)

In this problem, \(N \times D \leq 10^6\), so calculating this directly for all locations and all days is sufficiently fast.

Note that we are looking for the maximum of the “total error for each location”. Summing the maximum daily errors or finding the total sum of all errors will result in an incorrect answer.

Also, there is no need to store all actual temperatures \(A_{i,j}\) before calculating. It is sufficient to calculate the sum on the fly as you read each location’s row.

Algorithm

We can process it with the following steps:

1. Input \(N\) and \(D\).
2. Input the array of forecasted temperatures \(T\).
3. Initialize the variable ans representing the answer to \(0\).
4. For each location \(i\):
   • Retrieve the forecasted temperature ti = T[i].
   • Input the actual temperatures for \(D\) days at that location.
   • Set s = 0 and add abs(a - ti) for each actual temperature a.
   • Update ans with max(ans, s).
5. Finally, output ans.

Complexity

• Time Complexity: \(O(ND)\)
• Space Complexity: \(O(N)\)

We use \(O(N)\) memory to store the forecasted temperature array \(T\). Since the actual temperatures are processed while reading each row, there is no need to store all of them.

Implementation Details

Since the input size can be as large as \(N \times D \leq 10^6\), using sys.stdin.buffer.readline in Python is recommended for efficiency.

Additionally, the actual temperatures for each location can be processed on the fly as follows:

for a in map(int, input().split()):
    s += abs(a - ti)

This avoids having to store the entire \(A\) as a two-dimensional array.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, D = map(int, input().split())
    T = list(map(int, input().split()))

    ans = 0
    for i in range(N):
        ti = T[i]
        s = 0
        for a in map(int, input().split()):
            s += abs(a - ti)
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.