Overview

For each query, consider all cells reachable from the starting cell after exactly \(T\) operations, and find the maximum value of \(f(A_{i,p})\) over the values \(A_{i,p}\) written on those cells.

Since the reachable range forms a triangular shape, we preprocess to quickly compute interval maximums for each row.

Analysis

Shape of Reachable Cells

Let the starting cell be \((L, P)\).

In one operation, you can choose one of:

• Stay in place
• Move directly below
• Move diagonally below-right

Let \(d\) denote the number of times you actually moved downward.

• Moving down \(d\) times puts you on row \(L+d\).
• If \(r\) of those downward moves were to the lower-right, your position becomes \(P+r\).
• \(r\) can be freely chosen in the range \(0 \leq r \leq d\).

Therefore, the cells reachable after moving down exactly \(d\) times are:

\[ (L+d, P), (L+d, P+1), \ldots, (L+d, P+d) \]

Also, while the total number of operations is exactly \(T\), you can use “stay” to consume any remaining operations.
Thus, the number of downward moves \(d\) can range over:

\[ 0 \leq d \leq \min(T, N-L) \]

Therefore, the set of reachable cells is the collection of intervals for each \(d\):

\[ \text{Row } L+d \text{, positions } [P, P+d] \]

For example, when \((L, P) = (2, 1)\) and \(T = 2\), the reachable range is:

• \(d=0\): Position \(1\) on row \(2\)
• \(d=1\): Positions \(1\) to \(2\) on row \(3\)
• \(d=2\): Positions \(1\) to \(3\) on row \(4\)

Problem with the Naive Approach

If we enumerate all reachable cells, for a single query we may examine up to:

\[ 1 + 2 + \cdots + N = O(N^2) \]

cells.

Doing this for \(Q\) queries results in \(O(N^2Q)\), which is too slow.

Instead, we prepare a structure that can quickly compute “interval maximums” for each row.
Then, for each \(d\), we can find the maximum of:

\[ \text{Row } L+d \text{, positions } [P, P+d] \]

in \(O(1)\), allowing each query to be processed in \(O(N)\).

Since the constraint guarantees \(NQ \leq 10^7\), this is sufficiently fast.

Computing \(f(V)\)

\(f(V)\) is the maximum digit sum \(S(Y)\) among all integers \(Y\) satisfying \(0 \leq Y \leq V\).

Consider the decimal representation of \(V\).

Since \(Y \leq V\), consider the first digit where \(Y\) becomes smaller than \(V\). To maximize the digit sum, we decrease that digit by \(1\) compared to the corresponding digit of \(V\), and set all subsequent digits to \(9\).

In other words, the candidates are:

• \(V\) itself
• Numbers where some digit is decreased by \(1\) and all digits to its right are set to \(9\)

For example, if \(V=5123\), the candidates are:

• \(5123\)
• \(4999\)
• \(5099\)
• \(5119\)
• \(5122\)

Taking the maximum digit sum among these gives \(f(V)\).

Since \(V \leq 10^{18}\), there are at most \(19\) digits, so this can be computed sufficiently fast for each cell.

Algorithm

First, instead of using the cell values \(A_{i,p}\) directly, we precompute:

\[ B_{i,p} = f(A_{i,p}) \]

Then, to quickly compute interval maximums for each row, we build a Sparse Table.

In the Sparse Table, we define:

\[ \text{st}[k][i][p] \]

as:

\[ \text{The maximum value in the interval of length } 2^k \text{ starting from position } p \text{ on row } i \]

The transition is:

\[ \text{st}[k][i][p] = \max( \text{st}[k-1][i][p], \text{st}[k-1][i][p+2^{k-1}] ) \]

This allows us to answer any interval \([l, r]\) maximum in \(O(1)\).

Let \(\text{len}=r-l+1\) be the interval length, and:

\[ k = \lfloor \log_2 \text{len} \rfloor \]

Then:

\[ \max([l,r]) = \max( \text{st}[k][row][l], \text{st}[k][row][r-2^k+1] ) \]

For each query, we process as follows:

1. If \(P > L\), the starting cell does not exist, so output NA.
2. Otherwise, let:

$\( D = \min(T, N-L) \)$

1. For each \(d = 0, 1, \ldots, D\), find the maximum of:

$\( \text{Row } L+d \text{, interval } [P, P+d] \)$

1. Output the maximum among all of these as the answer.

Complexity

• Time complexity: \(O(N^2 \log N + NQ)\)
  • Computing \(f(A_{i,p})\) for each cell takes \(O(N^2)\) overall since each has at most \(19\) digits
  • Building the Sparse Table takes \(O(N^2 \log N)\)
  • Each query takes at most \(O(N)\), and since \(NQ \leq 10^7\), the total is \(O(NQ)\)
• Space complexity: \(O(N^2 \log N)\)

Implementation Notes

• \(T\) can be as large as \(10^9\), but the actual number of downward moves is at most \(N-L\), so we handle it as:

$\( D = \min(T, N-L) \)$

• Since \(A_{i,p}\) can be up to \(10^{18}\), use long long for input.

• The value of \(f(A_{i,p})\) is a digit sum, so it is at most a few hundred, and int is sufficient.

• The array size for the Sparse Table must be large enough to accommodate the constraint on \(N\).
  If \(N \leq 1000\), set MAXN to at least 1000 or more.

  Source Code

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

const int MAXN = 500;
const int LOG = 10;

static int st[LOG][MAXN + 2][MAXN + 2];
int lg2_table[MAXN + 2];

int calc_f(long long v) {
    string s = to_string(v);
    int n = (int)s.size();

    vector<int> pref(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + (s[i] - '0');
    }

    int ans = pref[n];
    for (int i = 0; i < n; i++) {
        int d = s[i] - '0';
        if (d > 0) {
            ans = max(ans, pref[i] + (d - 1) + 9 * (n - i - 1));
        }
    }
    return ans;
}

int row_max(int row, int l, int r) {
    int len = r - l + 1;
    int k = lg2_table[len];
    return max(st[k][row][l], st[k][row][r - (1 << k) + 1]);
}

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

    int N, Q;
    cin >> N >> Q;

    for (int i = 1; i <= N; i++) {
        for (int p = 1; p <= i; p++) {
            long long x;
            cin >> x;
            st[0][i][p] = calc_f(x);
        }
    }

    lg2_table[1] = 0;
    for (int i = 2; i <= N; i++) {
        lg2_table[i] = lg2_table[i / 2] + 1;
    }

    for (int k = 1; k < LOG; k++) {
        int len = 1 << k;
        if (len > N) break;
        int half = 1 << (k - 1);

        for (int row = 1; row <= N; row++) {
            for (int p = 1; p + len - 1 <= row; p++) {
                st[k][row][p] = max(st[k - 1][row][p], st[k - 1][row][p + half]);
            }
        }
    }

    while (Q--) {
        int L, P;
        long long T;
        cin >> L >> P >> T;

        if (P > L) {
            cout << "NA\n";
            continue;
        }

        int D = (int)min<long long>(T, N - L);
        int ans = 0;

        for (int d = 0; d <= D; d++) {
            int row = L + d;
            ans = max(ans, row_max(row, P, P + d));
        }

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

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.