fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int mod = 998244353;
  4.  
  5. int main() {
  6.     ios_base::sync_with_stdio(0);
  7.     cin.tie(0);
  8.  
  9.     int t;
  10.     cin >> t;
  11.     while (t--) {
  12.         int n, k;
  13.         cin >> n >> k;
  14.         int a[2][n + 1]; // збільшено розмір
  15.  
  16.         for (int i = 0; i < 2; i++) {
  17.             for (int j = 0; j < n; j++) {
  18.                 cin >> a[i][j];
  19.             }
  20.         }
  21.  
  22.         vector<vector<int>> dp(n + 2, vector<int>(k + 2, 0));
  23.         dp[n][0] = 1;
  24.  
  25.         for (int i = n; i >= 1; i--) {
  26.             for (int D = 0; D <= k + 1; D++) {
  27.                 if (a[0][i - 1] == -1 && a[1][i - 2] == -1) {
  28.                     for (int d = -k + 1; d <= k - 1; d++) {
  29.                         int i1 = i - 1;
  30.                         int D1 = max(0, D + d);
  31.                         D1 = min(D1, k + 1);
  32.                         if (D1 == 0 || d >= 0) {
  33.                             dp[i1][D1] = (dp[i1][D1] + dp[i][D]) % mod;
  34.                         }
  35.                     }
  36.                 } else if (a[0][i - 1] == -1 && a[1][i - 2] != -1) {
  37.                     int y = a[1][i - 2];
  38.                     for (int x = 1; x <= k; x++) {
  39.                         int d = x - y;
  40.                         int i1 = i - 1;
  41.                         int D1 = max(0, D + d);
  42.                         D1 = min(D1, k + 1);
  43.                         if (D1 == 0 || d >= 0) {
  44.                             dp[i1][D1] = (dp[i1][D1] + dp[i][D]) % mod;
  45.                         }
  46.                     }
  47.                 } else if (a[0][i - 1] != -1 && a[1][i - 2] == -1) {
  48.                     int x = a[0][i - 1];
  49.                     for (int y = 1; y <= k; y++) {
  50.                         int d = x - y;
  51.                         int i1 = i - 1;
  52.                         int D1 = max(0, D + d);
  53.                         D1 = min(D1, k + 1);
  54.                         if (D1 == 0 || d >= 0) {
  55.                             dp[i1][D1] = (dp[i1][D1] + dp[i][D]) % mod;
  56.                         }
  57.                     }
  58.                 } else {
  59.                     int x = a[0][i - 1];
  60.                     int y = a[1][i - 2];
  61.                     int d = x - y;
  62.                     int i1 = i - 1;
  63.                     int D1 = max(0, D + d);
  64.                     D1 = min(D1, k + 1);
  65.                     if (D1 == 0 || d >= 0) {
  66.                         dp[i1][D1] = (dp[i1][D1] + dp[i][D]) % mod;
  67.                     }
  68.                 }
  69.             }
  70.         }
  71.  
  72.         int ans = 0;
  73.         for (int i = 0; i <= k + 1; i++) {
  74.             ans = (ans + dp[0][i]) % mod;
  75.         }
  76.         cout << ans << '\n';
  77.     }
  78. }
  79.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
3
4 3
2 1 -1 2
2 -1 1 3
5 4
1 3 -1 4 2
-1 3 4 2 -1
10 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
stdout
copy 
3
16
553500593
https://ideone.com/F4ZjpG
problem BIT2, based on SPOJ submission 11034498 (C++ 4.3.2), 2014-02-09 15:54:15
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!