Summary

For each location, we calculate the “total forecast error,” which is the sum of the absolute differences between the forecast and actual temperatures over the given number of days, and find the maximum value among all locations.

Analysis

According to the problem statement, we need to calculate the total forecast error \(S_i = \sum_{j=1}^{D} |A_{i,j} - T_i|\) for each location \(i\).

Naively, one might want to store all actual temperatures \(A_{i,j}\) in a 2D array before calculating. However, this can be a waste of memory. The calculation of \(S_i\) is independent for each location \(i\), and we do not need to keep the data of other locations in memory. Therefore, we can significantly reduce memory usage by reading the inputs and calculating the absolute differences on the fly, updating the total sum as we go.

Also, looking at the maximum value of \(S_i\), the maximum forecast error per day is \(|50 - (-50)| = 100\). Even if this continues for the maximum number of days \(D = 10000\), the total is at most \(1,000,000\). Thus, it will not overflow a standard 32-bit signed integer (int), but using long long is a safe and reliable choice to prevent any potential issues.

Algorithm

1. Read the number of locations \(N\) and the number of days \(D\).
2. Read the forecast temperature \(T_i\) for each location into an array.
3. For each location \(i\) (from \(0\) to \(N-1\)), repeat the following process:
   • Initialize the total sum \(S\) to \(0\).
   • Read the actual temperature \(a\) for each of the \(D\) days one by one.
   • Calculate the absolute difference between \(T_i\) and \(a\), and add it to \(S\).
   • If \(S\) exceeds the current maximum value, update the maximum value.
4. After processing all locations, output the maximum value.

Complexity

• Time Complexity: \(O(N \times D)\) Since we read and process the inputs for all locations and days exactly once, the loop runs \(N \times D\) times. Since \(N \times D \leq 10^6\) according to the constraints, this can easily run within the time limit.
• Space Complexity: \(O(N)\) Instead of storing all actual temperatures, we only keep the forecast temperatures array T and the current input variable a. Thus, the space complexity is \(O(N)\).

Implementation Points

• Process input sequentially: Instead of storing the actual temperatures \(A_{i,j}\) in a 2D array in memory, we read them into a single variable (such as a in the code) inside the loop and use them directly for calculation. This minimizes memory consumption.

• Fast I/O: To handle a large amount of input using cin, we use ios_base::sync_with_stdio(false); and cin.tie(nullptr); to speed up the input reading.

• Data Type Selection: Although the calculated results fit within the int type, using long long (e.g., long long S = 0;, long long max_S = 0;) when dealing with cumulative sums is a safe implementation practice to prevent unexpected overflow.

  Source Code

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, D;
    if (!(cin >> N >> D)) return 0;
    
    vector<int> 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 S = 0;
        for (int j = 0; j < D; ++j) {
            int a;
            cin >> a;
            S += abs(a - T[i]);
        }
        if (S > max_S) {
            max_S = S;
        }
    }
    
    cout << max_S << "\n";
    return 0;
}

This editorial was generated by or-glm5.2-high.