102165: [AtCoder]ABC216 F - Max Sum Counting
Description
Score : $500$ points
Problem Statement
Given are sequences of $N$ integers each: $A = (A_1, \dots, A_N)$ and $B = (B_1, \dots, B_N)$. Find the number of non-empty subsets $S$ of $\{1,2,\ldots,N\}$ that satisfy the following condition:
- $\max_{i \in S} A_i \geq \sum_{i \in S} B_i$.
Since the count can be enormous, print it modulo $998244353$.
Constraints
- $1 \leq N \leq 5000$
- $1 \leq A_i,B_i \leq 5000$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$
Output
Print the number of subsets $S$ that satisfy the condition in the Problem Statement, modulo $998244353$.
Sample Input 1
2 3 1 1 2
Sample Output 1
2
$\{1,2,\ldots,N\}$ has three subsets: $\{1\}$, $\{2\}$, and $\{1,2\}$.
- For $S=\{1\}$, we have $\max_{i \in S} A_i=3$ and $\sum_{i \in S} B_i=1$.
- For $S=\{2\}$, we have $\max_{i \in S} A_i=1$ and $\sum_{i \in S} B_i=2$.
- For $S=\{1,2\}$, we have $\max_{i \in S} A_i=3$ and $\sum_{i \in S} B_i=3$.
Thus, the condition $\max_{i \in S} A_i \geq \sum_{i \in S} B_i$ is satisfied by two subsets: $\{1\}$ and $\{1,2\}$.
Sample Input 2
2 1 1 2 2
Sample Output 2
0
There may be no subsets that satisfy the condition.
Sample Input 3
20 1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247 4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017
Sample Output 3
476
Input
题意翻译
给出两个有 $n$ 个元素的序列 $a,b$，现在在 $1 - n$ 中选一些数构成集合 $S$，使得 $max_{i \in S} \space a_i \ge \sum_{i \in S} \space b_i$，问合法的集合 $S$ 的个数 $\mod 998244353$。 $1 \le N \le 5000,1 \le a_i,b_i \le 5000$.Output
问题描述
给出两个长度为$N$的整数序列$A = (A_1, \dots, A_N)$和$B = (B_1, \dots, B_N)$。找出满足以下条件的非空子集$S$的数量：
- $\max_{i \in S} A_i \geq \sum_{i \in S} B_i$。
由于计数可能非常大，请模$998244353$输出。
限制条件
- $1 \leq N \leq 5000$
- $1 \leq A_i,B_i \leq 5000$
- 输入中的所有值都是整数。
输入
输入从标准输入按以下格式给出：
$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$
输出
模$998244353$输出满足条件的子集$S$的数量。
样例输入1
2 3 1 1 2
样例输出1
2
集合$\{1,2,\ldots,N\}$有三个子集：$\{1\}$，$\{2\}$和$\{1,2\}$。
- 对于$S=\{1\}$，我们有$\max_{i \in S} A_i=3$和$\sum_{i \in S} B_i=1$。
- 对于$S=\{2\}$，我们有$\max_{i \in S} A_i=1$和$\sum_{i \in S} B_i=2$。
- 对于$S=\{1,2\}$，我们有$\max_{i \in S} A_i=3$和$\sum_{i \in S} B_i=3$。
因此，满足条件$\max_{i \in S} A_i \geq \sum_{i \in S} B_i$的子集有两个：$\{1\}$和$\{1,2\}$。
样例输入2
2 1 1 2 2
样例输出2
0
可能没有满足条件的子集。
样例输入3
20 1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247 4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017
样例输出3
476