Overview

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

Analysis

The total forecast error \(S_i\) for each location \(i\) can be expressed as follows, as described in the problem statement:

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

The value we want to find is the maximum value of \(S_i\) across all locations, which is \(\max(S_1, S_2, \ldots, S_N)\).

Looking at the constraints, the number of locations is \(N \le 10000\), the number of days is \(D \le 10000\), and we are given a very important constraint: \(N \times D \le 10^6\). If we calculate the error for all combinations of locations and days in a straightforward manner, the number of operations will be \(N \times D\). Since \(N \times D \le 10^6\), even with this naive brute-force approach, the total number of operations is at most around \(10^6\). For a typical programming contest time limit (usually 2 seconds), a loop with \(10^6\) iterations runs sufficiently fast (a few milliseconds to dozens of milliseconds). Therefore, this simple approach is correct and will pass.

Algorithm

1. Initialize a variable max_S to \(0\), which will store the maximum forecast error found so far.
2. Store the forecast temperatures \(T_1, T_2, \ldots, T_N\) for each location in an array (list).
3. For each location \(i\) (\(1 \le i \le N\)), perform the following steps in order:
   • Initialize a variable current_S to \(0\), which will store the total forecast error for location \(i\).
   • Read the actual temperatures \(A_{i, 1}, A_{i, 2}, \ldots, A_{i, D}\) for \(D\) days one by one.
   • Each time you read a value, calculate the forecast error \(|A_{i, j} - T_i|\) and add it to current_S.
   • After adding the values for all \(D\) days, compare max_S and current_S, and update max_S with the larger value (max_S = max(max_S, current_S)).
4. After processing all locations, output the value of max_S.

Complexity

• Time Complexity: \(O(N \times D)\) Since we iterate through \(D\) days of data for each location \(i\), the total number of loop iterations is \(N \times D\). Since \(N \times D \le 10^6\), this easily runs within the time limit.
• Space Complexity: \(O(N)\) We use an array of length \(N\) to store the forecast temperatures \(T\) for each location. Since we read each actual temperature \(A_{i, j}\) from the input one by one and process it on the fly without storing all of them in memory, we do not need to allocate a two-dimensional array (of size \(N \times D\)). This significantly reduces memory usage.

Implementation Points

• Saving Memory: If we store all actual temperatures \(A_{i, j}\) in memory (such as in a two-dimensional array), we would have to hold up to \(10^6\) elements, which consumes a lot of memory. As in this implementation, by running the inner loop (days \(j\)) inside the outer loop (location \(i\)) and reading \(A_{i, j}\) from standard input into a variable A on the fly, we can keep the space complexity at \(O(N)\).

• Fast I/O: Since the number of input integers can be up to about \(10^6\), which is relatively large, in C++ we disable the synchronization of standard I/O streams using ios_base::sync_with_stdio(false); cin.tie(NULL); to speed up the process. This prevents Time Limit Exceeded (TLE) caused by I/O bottlenecks.

  Source Code

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, D;
    if (!(cin >> N >> D)) return 0;

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

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

    cout << max_S << "\n";

    return 0;
}

This editorial was generated by gemini-3.5-flash-high.