fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #define ll long long
  5.  
  6. using namespace std;
  7. const int MOD = 1000000007;
  8. const int Mmax = 4004, Nmax = 4004;
  9. // using static array instead of vector to decrease the running time
  10. int Ri[Mmax][Nmax], Do[Mmax][Nmax], A[Mmax], B[Nmax];
  11. ll res[Mmax][Nmax];
  12.  
  13. int main()
  14. {
  15.     if (fopen("JUMP.INP", "r")) {
  16.         freopen("JUMP.INP", "r", stdin);
  17.         freopen("JUMP.OUT", "w", stdout);
  18.     }
  19.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  20.     int m, n, k;
  21.     // using scanf() instead of cin to decrease the running time
  22.     scanf("%d %d %d", &m, &n, &k);
  23.     for (int i = 1; i <= m; ++i) {
  24.         scanf("%d", &A[i]);
  25.         A[i] %= k; // we take modulo of A[i] first for later purpose
  26.     }
  27.     for (int i = 1; i <= n; ++i) {
  28.         scanf("%d", &B[i]);
  29.         B[i] %= k; // we take modulo of B[i] first for later purpose
  30.     }
  31.     res[m][n] = Ri[m][n] = Do[m][n] = 1;
  32.     for (int i = m; i > 0; --i) {
  33.         for (int j = n; j > 0; --j) {
  34.             int val = A[i] + B[j];
  35.             if (val >= k) val -= k; // calculate (A[i] + B[j]) % k avoid using mod '%'
  36.             res[i][j] += Ri[i][j + 1] - Ri[i][min(j + 2 + val, n + 1)] + MOD;
  37.             res[i][j] += Do[i + 1][j] - Do[min(i + 2 + val, m + 1)][j] + MOD;
  38.             while (res[i][j] >= MOD) res[i][j] -= MOD; // calculate res[i][j] % MOD avoid using mod '%'
  39.             Ri[i][j] = Ri[i][j + 1] + res[i][j];
  40.             Do[i][j] = Do[i + 1][j] + res[i][j];
  41.             if (Ri[i][j] >= MOD) Ri[i][j] -= MOD; // calculate Ri[i][j] % MOD avoid using mod '%'
  42.             if (Do[i][j] >= MOD) Do[i][j] -= MOD; // calculate Do[i][j] % MOD avoid using mod '%'
  43.         }
  44.     }
  45.     cout << res[1][1];
  46.     return 0;
  47. }
Runtime error #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ChQ0oA
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!