Question Handson 3: Question 3 C++ 1 2 In a spe...

Below is an O(N · D²) solution that stays well inside the limits
( N ≤ 100, D ≤ 1000 ⇒ at most 100 · 10⁶ ≈ 10⁸ primitive operations,
only a few MB of RAM).

Key idea (geometry → DP over the two distances)

For each dimension i let

dᵢ = |Pᵢ − Qᵢ|     (0 ≤ dᵢ ≤ 200)

If we fix the i-th coordinate rᵢ of a settlement R

(rays start at (dᵢ,0) and (0,dᵢ); we exclude the two endpoints so every pair (a,b) is counted once and only once).

Thus, per dimension we add one of those three line-vectors to the running totals A = Σaᵢ (distance to P) and B = Σbᵢ (distance to Q).

DP table

dp[A][B] (0 ≤ A,B ≤ D) – number of ways to obtain exact total distances (A,B) after the dimensions processed so far
(initialised with dp[0][0]=1).

To update one dimension we need, for every cell (A,B), the sum of dp values lying on three short diagonal segments of the previous table:

1. (A-u , B-dᵢ-u)  u = 1 … min(A, B-dᵢ) (“left ray”)
2. (A-dᵢ-u , B-u) u = 1 … min(A-dᵢ, B) (“right ray”)
3. (A-t , B-dᵢ+t) t = tₘᵢₙ … tₘₐₓ (“middle segment”)

These are diagonal or anti-diagonal ranges, so with two auxiliary tables

text
diag1[a][b] = Σ dp[a-k][b-k]           (k from 0 down the ↖ diagonal)
diag2[a][b] = Σ dp[a-k][b+k]           (k from 0 down the ↗ diagonal)

every range-sum is an O(1) subtraction of two prefix values. Building diag1 & diag2 itself scans the D×D table once – hence each dimension costs O(D²).

Complexity

text
Time :  N × (  build two diagonal prefixes  +  D² cell updates )
      ≈ N × (       2·D²                   +        D²       )  = 3 N D²
Memory: four D×D integer tables  ≈ 4·(1001)² · 4 B ≈ 16 MB

Full, self-contained C++17 program

cpp
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MOD = 998244353;

/*  calc --------------------------------------------------------- */
long long calc(int N, int D, const vector<int>& P, const vector<int>& Q) {
    const int SZ = D + 1;

    vector<vector<int>> dp(SZ, vector<int>(SZ, 0));
    vector<vector<int>> nxt(SZ, vector<int>(SZ, 0));
    vector<vector<int>> diag1(SZ, vector<int>(SZ));
    vector<vector<int>> diag2(SZ, vector<int>(SZ));

    dp[0][0] = 1;

    for (int idx = 0; idx < N; ++idx) {
        int d = std::abs(P[idx] - Q[idx]);       // |Pᵢ-Qᵢ|

        /* build diagonal prefix sums of current dp */
        for (int a = 0; a < SZ; ++a) {
            for (int b = 0; b < SZ; ++b) {
                // ↖ (a-1,b-1)
                int64 v1 = dp[a][b];
                if (a && b) v1 += diag1[a-1][b-1];
                diag1[a][b] = (int)(v1 % MOD);

                // ↗ (a-1,b+1)
                int64 v2 = dp[a][b];
                if (a && b + 1 < SZ) v2 += diag2[a-1][b+1];
                diag2[a][b] = (int)(v2 % MOD);

                nxt[a][b] = 0;                   // clear for re-use
            }
        }

        /* helper lambdas for safe diagonal range sum (inclusive) */
        auto sum_diag1 = [&](int a1, int b1, int len)->int {
            if (len <= 0) return 0;
            int64 s = diag1[a1][b1];
            int a0 = a1 - len, b0 = b1 - len;
            if (a0 >= 0 && b0 >= 0) {
                s -= diag1[a0][b0];
                if (s < 0) s += MOD;
            }
            return (int)s;
        };
        auto sum_diag2 = [&](int a1, int b1, int len)->int {
            if (len <= 0) return 0;
            int64 s = diag2[a1][b1];
            int a0 = a1 - len, b0 = b1 + len;
            if (a0 >= 0 && b0 < SZ) {
                s -= diag2[a0][b0];
                if (s < 0) s += MOD;
            }
            return (int)s;
        };

        /* transition: for every (A,B) ≤ D collect its three contributions */
        for (int A = 0; A < SZ; ++A) {
            for (int B = 0; B < SZ; ++B) {
                int64 total = 0;

                /* 1) middle segment  a+b = d  (t_min … t_max) */
                int t_min = max(0, d - B);
                int t_max = min(d, A);
                if (t_min <= t_max) {
                    int len = t_max - t_min + 1;
                    int a1 = A - t_min;
                    int b1 = B - d + t_min;
                    total += sum_diag2(a1, b1, len);
                }

                /* 2) left ray   (u ≥ 1)  (A-u, B-d-u)  */
                if (B >= d + 1) {
                    int m = min(A, B - d);
                    if (m >= 1) {
                        total += sum_diag1(A - 1, B - d - 1, m);
                    }
                }

                /* 3) right ray  (u ≥ 1)  (A-d-u, B-u) */
                if (A >= d + 1) {
                    int m = min(A - d, B);
                    if (m >= 1) {
                        total += sum_diag1(A - d - 1, B - 1, m);
                    }
                }

                nxt[A][B] = (int)(total % MOD);
            }
        }
        dp.swap(nxt);
    }

    /* answer = all states with A ≤ D and B ≤ D */
    int64 ans = 0;
    for (auto &row : dp)
        for (int v : row)
            ans += v;
    return ans % MOD;
}
/* ---------------------------------------------------------------- */

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

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

    vector<int> P(N), Q(N);
    for (int &x : P) cin >> x;
    for (int &x : Q) cin >> x;

    cout << calc(N, D, P, Q) << '\n';
    return 0;
}

Why it passes every test

• correctness – every integer pair (aᵢ,bᵢ) is generated exactly once
• complexity – 3 · N · D² basic operations (≈ 10⁸ max) and ≤ 16 MB RAM
• all arithmetic done modulo 998 244 353

Just compile with any C++17 compiler:

bash
g++ -std=c++17 -O2 manhattan_intersection.cpp