AT_abc216_f.[ABC216F] Max Sum Counting

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定长度为 $N$ 的数列 $A = (A_1, \dots, A_N)$ 和 $B = (B_1, \dots, B_N)$ 。请计算满足下述条件的 $\{1,2,\ldots,N\}$ 的非空子集 $S$ 的个数：

$\max_{i \in S} A_i \geq \sum_{i \in S} B_i$

由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入格式

输入通过标准输入以以下格式给出。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

请输出满足题目条件的 $S$ 的个数对 $998244353$ 取模的结果。

输入输出样例

输入#1
```
2
3 1
1 2
```
输出#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

说明/提示

限制条件

$1 \leq N \leq 5000$
$1 \leq A_i, B_i \leq 5000$
输入均为整数

样例解释 1

$\{1,2,\ldots,N\}$ 的非空子集有 $\{1\}$ 、 $\{2\}$ 、 $\{1,2\}$ 共 $3$ 种。

当 $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$ 的 $S$ 有 $\{1\}$ 和 $\{1,2\}$ 共 $2$ 种。

样例解释 2

也可能不存在满足条件的 $S$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页