Hi everyone Hope you're doing great!

Yesterday, in the Div1+Div2 contest held on July 20, 2025, the E problem had an interesting path to optimize the constraints and ordering of computations.
With tighter constraints and better prefix handling, I managed to push the solution down to ~62ms, even for (n, k) limits.

330003602

Source Code

```cpp

include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 998244353; const int N = 504; int A[N], B[N], n, k;

ll dp[N], pre[N], pree[N], dp1[N];

define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main() { fast_io int T; cin >> T; while (T--) { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> A[i]; for (int i = 1; i <= n; i++) cin >> B[i];

dp1[0] = 1;
    for (int i = 1; i <= n - 1; i++) {
        pre[0] = dp[0];
        pree[0] = dp[0] * (k + 1) % mod;
        for (int j = 1; j <= k; j++) {
            pre[j] = (pre[j - 1] + dp[j]) % mod;
            pree[j] = (pree[j - 1] + dp[j] * (k + 1 - j)) % mod;
        }

        if (A[i + 1] == -1 && B[i] == -1) {
            for (int j = 0; j <= k; j++) {
                if (j == 0) dp[j] = pree[k] - pre[k] + mod;
                else dp[j] = (pree[k] - pree[j - 1] + mod + (pre[k] - pre[j - 1] + mod) * (j - 1) + mod) % mod;
                if (j != 0) {
                    dp[j] = (dp[j] + pre[k] * (k - j) + dp1[i - 1] * (k - j)) % mod;
                }
            }
            dp1[i] = dp1[i - 1] * (k * k - k * (k - 1) / 2) % mod;
            continue;
        }

        int l = (A[i + 1] == -1 ? 1 : A[i + 1]) - (B[i] == -1 ? k : B[i]);
        int r = (A[i + 1] == -1 ? k : A[i + 1]) - (B[i] == -1 ? 1 : B[i]);

        for (int j = 0; j <= k; j++) {
            int l2 = max(j + l, j) - 1, r2 = min(k, j + r);
            if (l2 < r2) dp[j] = ((r2 < 0 ? 0 : pre[r2]) - (l2 < 0 ? 0 : pre[l2]) + mod) % mod;
            else dp[j] = 0;
            if (-r <= j && j <= -l && j != 0) dp[j] = (dp[j] + dp1[i - 1] + pre[k]) % mod;
        }

        dp1[i] = dp1[i - 1] * max(0, r + 1 - max(l, 0)) % mod;
    }

    ll ans = dp1[n - 1];
    for (int i = 0; i <= k; i++) ans = (ans + dp[i]) % mod;
    ans = ans * (A[1] == -1 ? k : 1) % mod * (B[n] == -1 ? k : 1) % mod;

    cout << ans << '\n';

    for (int i = 0; i <= k; i++) dp[i] = 0;
}

}