← 返回题目列表

Codeforces · 1542/D

D. 优先队列

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

给定一个序列 $$$A$$$,其中元素的形式为 + x 或 -,其中 $$$x$$$ 是整数。

对于这样的序列 $$$S$$$,其元素采用 + x 或 - 的形式,定义 $$$f(S)$$$ 如下:

- 从第一个到最后一个迭代 $$$S$$$ 的元素,并在迭代时维护一个多重集 $$$T$$$。
- 对于每个元素,如果其形式为 + x,则将 $$$x$$$ 添加到 $$$T$$$;否则,删除 $$$T$$$ 中的最小元素(如果 $$$T$$$ 为空,则不执行任何操作)。
- 迭代所有 $$$S$$$ 的元素后,计算 $$$T$$$ 中所有元素的总和。 $$$f(S)$$$ 被定义为总和。

如果 $$$b$$$ 可以通过删除零个或多个元素而不改变剩余元素的顺序从 $$$a$$$ 导出,则序列 $$$b$$$ 是序列 $$$a$$$ 的子序列。对于所有 $$$A$$$ 的子序列 $$$B$$$,计算 $$$f(B)$$$ 的总和,以 $$$998\,244\,353$$$ 为模。

输入

第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 500$$$) — $$$A$$$ 的长度。

接下来的 $$$n$$$ 行均以运算符 + 或 - 开头。如果运算符是 +,则其后跟随一个整数 $$$x$$$ ($$$1\le x<998\,244\,353$$$)。这些 $$$n$$$ 行中的第 $$$i$$$ 行描述了 $$$A$$$ 中的第 $$$i$$$ 元素。

输出

打印一个整数,即问题的答案,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

4
-
+ 1
+ 2
-

输出 #1

16

输入 #2

15
+ 2432543
-
+ 4567886
+ 65638788
-
+ 578943
-
-
+ 62356680
-
+ 711111
-
+ 998244352
-
-

输出 #2

750759115

注意

在第一个示例中,以下是所有可能的 $$$B$$$ 和 $$$f(B)$$$ 对:

- $$$B=$$$ {},$$$f(B)=0$$$。
- $$$B=$$$ {-},$$$f(B)=0$$$。
- $$$B=$$$ {+ 1, -}, $$$f(B)=0$$$。
- $$$B=$$$ {-, + 1, -}, $$$f(B)=0$$$。
- $$$B=$$$ {+ 2, -}, $$$f(B)=0$$$。
- $$$B=$$$ {-, + 2, -}, $$$f(B)=0$$$。
- $$$B=$$$ {-},$$$f(B)=0$$$。
- $$$B=$$$ {-, -}, $$$f(B)=0$$$。
- $$$B=$$$ {+ 1, + 2},$$$f(B)=3$$$。
- $$$B=$$$ {+ 1, + 2, -}, $$$f(B)=2$$$。
- $$$B=$$$ {-, + 1, + 2}, $$$f(B)=3$$$。
- $$$B=$$$ {-, + 1, + 2, -}, $$$f(B)=2$$$。
- $$$B=$$$ {-, + 1},$$$f(B)=1$$$。
- $$$B=$$$ {+ 1},$$$f(B)=1$$$。
- $$$B=$$$ {-, + 2},$$$f(B)=2$$$。
- $$$B=$$$ {+ 2},$$$f(B)=2$$$。

这些值的总和为 $$$16$$$。