Use Udon Coupon

AtCoder

IDarc204_a

Time2000ms

Memory256MB

Difficulty—

You are given positive integers $N, L, R$ and length-$N$ positive integer sequences $A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N})$. Using a sequence $Q$ initialized as empty, a variable $C$ initialized to $0$, and a variable $i$ initialized to $1$, perform the following operation $2N$ times. * Choose one of the following actions $1, 2$ and perform it. * Action $1$ : Insert $i$ at the end of $Q$, replace $C$ with $\max(0, C - A_{i})$. Then, increase $i$ by $1$. This action can only be performed when $i$ before the operation is at most $N$. * Action $2$ : Let $x$ be the first number in $Q$, and add $B_{x}$ to $C$. Then, remove the first element of $Q$. This action can only be performed when $Q$ before the operation is not empty. Find the number, modulo $998244353$, of ways to perform $2N$ operations such that the final value of $C$ is between $L$ and $R$, inclusive. ## Constraints * $1\leq N\leq 5000$ * $1\leq L \leq R \leq \sum B$ * $1\leq A_{i}\leq 5000$ * $1\leq B_{i}\leq 5000$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $L$ $R$ $A_{1}$ $A_{2}$ $\dots$ $A_{N}$ $B_{1}$ $B_{2}$ $\dots$ $B_{N}$ [samples]

Samples

Input #1

2 100 1000
2001 167
924 178

Output #1

1

For example, you can perform four operations as follows.

*   Perform action $1$. Then, $Q = (1), C = 0, i = 2$.
*   Perform action $2$. Then, $Q = (), C = 924, i = 2$.
*   Perform action $1$. Then, $Q = (2), C = 757, i = 3$.
*   Perform action $2$. Then, $Q = (), C = 935, i = 3$.

Performing operations as above makes the final value of $C$ between $100$ and $1000$ (inclusive). This is the only such way to perform operations, so output $1$.

Input #2

3 10 10
1 6 7
9 2 4

Output #2

Input #3

15 167 924
122 122 111 85 97 108 115 82 84 82 105 103 113 102 135
116 122 110 106 71 85 70 94 86 110 73 97 101 86 73

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Use Udon Coupon",
    "description": {
      "content": "You are given positive integers $N, L, R$ and length-$N$ positive integer sequences $A = (A_{1}, A_{2}, \\dots, A_{N}), B = (B_{1}, B_{2}, \\dots, B_{N})$. Using a sequence $Q$ initialized as empty, a v",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc204_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given positive integers $N, L, R$ and length-$N$ positive integer sequences $A = (A_{1}, A_{2}, \\dots, A_{N}), B = (B_{1}, B_{2}, \\dots, B_{N})$.\nUsing a sequence $Q$ initialized as empty, a v...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments