Overview

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

Analysis

The total forecast error for location \(i\) is:

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

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

1. Look at the forecasted temperature \(T_i\) for location \(i\).
2. Read the actual temperatures \(A_{i,j}\) for \(D\) days.
3. Add \(|A_{i,j} - T_i|\) for each day.
4. Update the maximum answer with this total sum.

For example, if the forecasted temperature for a location is \(10\) degrees and the actual temperatures are \(7, 12, 20\) degrees:

\(|7 - 10| + |12 - 10| + |20 - 10| = 3 + 2 + 10 = 15\)

Under the constraints, \(N \times D \leq 10^6\), so directly calculating this for all locations and all days is fast enough to pass within the time limit.

Also, there is no need to store the entire grid of actual temperatures \(A\). We can compute the sum for each location on the fly while reading the input.

Algorithm

We can compute the answer using the following steps:

1. Input \(N\) and \(D\).
2. Store the forecasted temperatures \(T_1, T_2, \ldots, T_N\) in an array.
3. Initialize the answer ans to \(0\).
4. For each location \(i\):
   • Initialize the sum sum to \(0\).
   • Read the actual temperatures \(A\) for \(D\) days sequentially.
   • Add the error by sum += abs(A - T[i]).
   • Update the maximum value with ans = max(ans, sum).
5. Finally, output ans.

Complexity

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

We use \(O(N)\) memory to store the forecasted temperatures \(T\). Since the actual temperatures \(A\) are processed on the fly as they are read, there is no need to store all of them.

Implementation Points

• Since the error is an absolute value, we use abs(A - T[i]).
• You need to reset the total sum to \(0\) for each location.
• The maximum possible sum is around \(100 \times 10000 = 10^6\), which fits in a standard 32-bit int, but using long long is a safe choice.
• Since the input size can be relatively large, we can include the following in C++ for fast I/O:

ios::sync_with_stdio(false);
cin.tie(nullptr);

Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D;
    cin >> N >> D;

    vector<int> T(N);
    for (int i = 0; i < N; i++) cin >> T[i];

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        long long sum = 0;
        for (int j = 0; j < D; j++) {
            int A;
            cin >> A;
            sum += abs(A - T[i]);
        }
        ans = max(ans, sum);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.