Priority Queue
Contest: Codeforces Round 729 (Div. 2)
Difficulty rating: 2200
Tags: combinatorics, dp, implementation, math, ternary search

You are given a sequence $$$A$$$, where its elements are either in the form + x or -, where $$$x$$$ is an integer.

For such a sequence $$$S$$$ where its elements are either in the form + x or -, define $$$f(S)$$$ as follows:

- iterate through $$$S$$$'s elements from the first one to the last one, and maintain a multiset $$$T$$$ as you iterate through it.
- for each element, if it's in the form + x, add $$$x$$$ to $$$T$$$; otherwise, erase the smallest element from $$$T$$$ (if $$$T$$$ is empty, do nothing).
- after iterating through all $$$S$$$'s elements, compute the sum of all elements in $$$T$$$. $$$f(S)$$$ is defined as the sum.

The sequence $$$b$$$ is a subsequence of the sequence $$$a$$$ if $$$b$$$ can be derived from $$$a$$$ by removing zero or more elements without changing the order of the remaining elements. For all $$$A$$$'s subsequences $$$B$$$, compute the sum of $$$f(B)$$$, modulo $$$998\,244\,353$$$.

Input format:
The first line contains an integer $$$n$$$ ($$$1\leq n\leq 500$$$) — the length of $$$A$$$.

Each of the next $$$n$$$ lines begins with an operator + or -. If the operator is +, then it's followed by an integer $$$x$$$ ($$$1\le x<998\,244\,353$$$). The $$$i$$$-th line of those $$$n$$$ lines describes the $$$i$$$-th element in $$$A$$$.

Output format:
Print one integer, which is the answer to the problem, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example, the following are all possible pairs of $$$B$$$ and $$$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$$$.

The sum of these values is $$$16$$$.

Example input:
4
-
+ 1
+ 2
-

Example output:
16

Example input:
15
+ 2432543
-
+ 4567886
+ 65638788
-
+ 578943
-
-
+ 62356680
-
+ 711111
-
+ 998244352
-
-

Example output:
750759115

Editorial:
Let's say we have picked the $$$x$$$ in the $$$I$$$-th operation, call it $$$X$$$. Then, the subsequence we choose must satisfy the following conditions:
• It must contain the $$$i$$$-th operation (otherwise $$$X$$$ won't be added).
• Let $$$s$$$ denote the number of numbers less than $$$X$$$ in the current $$$T$$$. Whenever we meet a '-' element in $$$S$$$ after the $$$i$$$-th operation, $$$s$$$ should be greater than $$$0$$$.
With those conditions, we can come up with the following dp.
Let $$$f(i,j)$$$ denote the number of subsequences of $$$a[1...i]$$$, that if we maintain $$$T$$$ with the subsequence, $$$s$$$ will become $$$j$$$.
Then we have the following transitions:
• $$$f(i-1,j)\to f(i,j)$$$ (when we don't include the $$$i$$$-th element is $$$S$$$, here $$$i\ne I$$$)
• $$$f(i-1,j)\to f(i,\max(j-1,0))$$$ (here, $$$i<I$$$, and the $$$i$$$-th element of $$$A$$$ is '-', so the number of numbers in $$$T$$$ less than $$$x$$$ decreases by one. If there is no such number, $$$s$$$ remains $$$0$$$)
• $$$f(i-1,j)\to f(i,j-1)$$$ (here, $$$i>I$$$, and and the $$$i$$$-th element of $$$A$$$ is '-', so the number of numbers in $$$T$$$ less than $$$x$$$ decreases by one.)
• $$$f(i-1,j)\to f(i,j)$$$ (here, the $$$i$$$-th element of $$$A$$$ is '+' and its $$$x$$$ is greater than $$$X$$$)
• $$$f(i-1,j)\to f(i,j+1)$$$ (here, the $$$i$$$-th element of $$$A$$$ is '+' and its $$$x$$$ is less than $$$x$$$ or [equal to $$$x$$$ but $$$i>I$$$] ) [this is to deal with same elements]
Then we add $$$ans$$$ by $$$X\times \sum_{i\ge 0} f(n,i)$$$.
The time complexity is $$$O(n^3)$$$.