← 返回题目列表

AtCoder · arc204_a

A. 使用乌冬面优惠券

中文机器翻译题面 查看原题

分数: 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