Manhattan Cafe

AtCoder

IDabc265_f

Time6000ms

Memory256MB

Difficulty—

In an $N$\-dimensional space, the Manhattan distance $d(x,y)$ between two points $x=(x_1, x_2, \dots, x_N)$ and $y = (y_1, y_2, \dots, y_N)$ is defined by: $\displaystyle d(x,y)=\sum_{i=1}^n \vert x_i - y_i \vert.$ A point $x=(x_1, x_2, \dots, x_N)$ is said to be a lattice point if the components $x_1, x_2, \dots, x_N$ are all integers. You are given lattice points $p=(p_1, p_2, \dots, p_N)$ and $q = (q_1, q_2, \dots, q_N)$ in an $N$\-dimensional space. How many lattice points $r$ satisfy $d(p,r) \leq D$ and $d(q,r) \leq D$? Find the count modulo $998244353$. ## Constraints * $1 \leq N \leq 100$ * $0 \leq D \leq 1000$ * $-1000 \leq p_i, q_i \leq 1000$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $D$ $p_1$ $p_2$ $\dots$ $p_N$ $q_1$ $q_2$ $\dots$ $q_N$ [samples]

Samples

Input #1

1 5
0
3

Output #1

8

When $N=1$, we consider points in a one-dimensional space, that is, on a number line.  
$8$ lattice points satisfy the conditions: $-2,-1,0,1,2,3,4,5$.

Input #2

3 10
2 6 5
2 1 2

Output #2

Input #3

10 100
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8

Output #3

145428186

API Response (JSON)

{
  "problem": {
    "name": "Manhattan Cafe",
    "description": {
      "content": "In an $N$\\-dimensional space, the Manhattan distance $d(x,y)$ between two points $x=(x_1, x_2, \\dots, x_N)$ and $y = (y_1, y_2, \\dots, y_N)$ is defined by: $\\displaystyle d(x,y)=\\sum_{i=1}^n \\vert x_",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc265_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In an $N$\\-dimensional space, the Manhattan distance $d(x,y)$ between two points $x=(x_1, x_2, \\dots, x_N)$ and $y = (y_1, y_2, \\dots, y_N)$ is defined by:\n\n$\\displaystyle d(x,y)=\\sum_{i=1}^n \\vert x_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments