P10143 [WC2024] Code Blockage

To commemorate the discontinued Code Jam, Little $\beth$ is preparing a “Code Blockage Memorial Contest”. Little $\beth$'s friend Little $\mho$ also comes to watch, so Little $\beth$ wants to predict Little $\mho$'s result. The contest lasts $T$ seconds and has $n$ problems. The score of problem $i(1 \le i \le n)$ is $a_i$, and Little $\beth$ predicts that Little $\mho$ needs $t_i$ seconds to finish it. There are two types of problems: visible-result and invisible-result. For an invisible-result problem, you can only know the judging result after the contest ends, while for a visible-result problem, you get the judging result immediately after submission. Little $\beth$ has not yet decided the type of each problem. Since Little $\mho$ never writes a checker for stress testing, they will first finish all visible-result problems in increasing order of index, and then finish all invisible-result problems in increasing order of index. Little $\mho$ will spend $t_i$ seconds to finish problem $i$. If the total time spent on problem $i$ and all problems finished before it is **not greater than** $T$, then Little $\mho$ will **make a submission** on problem $i$. Since every submission by Little $\mho$ is accepted (AC), Little $\beth$ wants to know, over all $2^n$ ways to determine the types of the $n$ problems, the sum of the total scores that Little $\mho$ can get. Since the answer can be very large, output it modulo $998244353$.

The first line contains three integers $c, n, T$, representing the test point index, the number of problems, and the contest duration. In the sample, $c$ indicates that it satisfies the same constraints as test point $c$. The second line contains $n$ integers $a_1, a_2, \cdots , a_n$, representing the score of each problem. The third line contains $n$ integers $t_1, t_2, \cdots , t_n$, representing the time Little $\mho$ needs for each problem.

Output one integer, representing, over all ways to determine the problem types, the sum of the total scores Little $\mho$ can obtain, modulo $998244353$.

**Sample 1 Explanation** We use a $01$ sequence of length $3$ to represent the problem types, where $1$ means visible-result and $0$ means invisible-result. - $(0, 0, 0)(1, 0, 0)(1, 1, 0)(1, 1, 1)$: in these four cases, Little $\mho$ solves problems in increasing order of index, submissions are made on the first two problems, and the score sum is $5$. - $(0, 1, 0)$: Little $\mho$ solves in the order $213$, submissions are made on the first two solved problems, and the score sum is $5$. - $(0, 0, 1)$: Little $\mho$ solves in the order $312$, submissions are made on the first and third problems, and the score sum is $6$. - $(1, 0, 1)$: Little $\mho$ solves in the order $132$, submissions are made on the first and third problems, and the score sum is $6$. - $(0, 1, 1)$: Little $\mho$ solves in the order $231$, only the second problem has a submission, and the score sum is $3$. Therefore, the answer is $(5 \times 4 + 5 + 6 + 6 + 3) \bmod 998244353 = 40$. ### Constraints For all testdata: - $1\le n\le 200$. - $1\le T\le 3\times 10^5$. - $\forall 1\le i\le n , 1\le a_i\le 3\times 10^5$. - $\forall 1\le i\le n, 1\le t_i\le T$. | Test Point Index | $n\le $ | $T\le $ | Special Property A | Special Property B | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1\sim 4$ | $15$ | $10^2$ | No | No | | $5\sim 7$ | $200$ | $3\times 10^5$ | Yes | Yes | | $8,9$ | $200$ | $3\times 10^5$ | Yes | No | | $10\sim 13$ | $200$ | $3\times 10^5$ | No | Yes | | $14\sim 16$ | $50$ | $10^3$ | No | No | | $17,18$ | $10^2$ | $10^4$ | No | No | | $19,20$ | $200$ | $3\times 10^5$ | No | No | - Special Property A: $\forall 1 \le i \le n, a_i = 1$. - Special Property B: $\forall 1 \le i \le n, t_i = 1$. ### Afterword “Why are all problems in your contest invisible-result?” Translated by ChatGPT 5