分数: 700 点
问题陈述
给你正整数 N, L, R 和长度-N 正整数序列 A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N}).
使用序列 Q 初始化为空,一个变量 C 初始化为 0和一个变量 i 初始化为 1,执行以下操作 2N 次。
- 选择以下操作之一 1, 2 并执行它。
- 行动 1 :插入 i 结束时 Q,替换 C 与 \max(0, C - A_{i})。然后,增加 i by 1。此操作只能在以下情况下执行 i 操作前最多 N.
- 行动 2 :让 x 是第一个数字 Q,并添加 B_{x} to C。然后,删除第一个元素 Q。此操作只能在以下情况下执行 Q 操作前不为空。
求模数 998244353,执行方法 2N 操作使得最终值 C 介于 L 和 R,包括在内。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N L R
A_{1} A_{2} \dots A_{N}
B_{1} B_{2} \dots B_{N}
输出
输出答案。
示例输入 1
2 100 1000 2001 167 924 178
示例输出 1
1
例如,您可以执行如下四种操作。
- 执行操作 1。然后, Q = (1), C = 0, i = 2.
- 执行操作 2。然后, Q = (), C = 924, i = 2.
- 执行操作 1。然后, Q = (2), C = 757, i = 3.
- 执行操作 2。然后, Q = (), C = 935, i = 3.
执行上述操作使得最终值为 C 之间 100 和 1000 (含)。这是执行操作的唯一方式,因此输出 1.
示例输入 2
3 10 10 1 6 7 9 2 4
示例输出 2
0
示例输入 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
示例输出 3
9576277