AT_joigsp2025_i.ティーパーティー (Tea Party)

通过率：0%

AC君温馨提醒

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

题目描述

葵计划举办一场茶会。预计包含葵在内共有 $M$ 人参加，所有参与者编号为 $1$ 到 $M$ 。葵打算给每位参与者分发 $1$ 块蛋糕和 $1$ 杯红茶。

为了茶会，葵准备了 $N$ 块蛋糕（ $N \geq M$ ）和 $M$ 杯红茶。蛋糕编号为 $1$ 到 $N$ ，红茶编号为 $1$ 到 $M$ 。第 $i$ 块蛋糕（ $1 \leq i \leq N$ ）的品牌为 $A_i$ ，美味度为 $B_i$ 。第 $j$ 杯红茶（ $1 \leq j \leq M$ ）的品牌为 $C_j$ ，美味度为 $D_j$ 。葵希望分配蛋糕和红茶，使所有参与者的幸福度总和尽可能大。

若给第 $k$ 位参与者（ $1 \leq k \leq M$ ）分配第 $i$ 块蛋糕（ $1 \leq i \leq N$ ）和第 $j$ 杯红茶（ $1 \leq j \leq M$ ），参与者 $k$ 的幸福度计算如下：

若 $A_i = C_j$ ，则参与者 $k$ 的幸福度为 $B_i + D_j$ 。
若 $A_i \neq C_j$ ，则参与者 $k$ 的幸福度为 $B_i$ 。

请在合理分配蛋糕与红茶的情况下，求所有参与者幸福度总和的最大可能值。未分发出去的蛋糕可以留给葵以后享用，无需考虑。

输入格式

输入为以下格式，从标准输入中读取：

$N \ M \ A_1 \ A_2 \ \cdots \ A_N \ B_1 \ B_2 \ \cdots \ B_N \ C_1 \ C_2 \ \cdots \ C_M \ D_1 \ D_2 \ \cdots \ D_M$

输出格式

请输出一行，表示在合理分配蛋糕和红茶时，所有参与者幸福度总和的最大可能值。

输入输出样例

输入#1
```
4 3
1 1 2 3
2 1 2 4
1 1 2
3 1 1
```
输出#1
```
12
```

输入#2

5 3
1 2 3 4 5
4695 53325 57544 74342 81986
1 2 3
59037 23296 16434

输出#2

输入#3
```
4 3
2 1 3 1
52 49 72 31
3 1 3
0 0 0
```
输出#3
```
173
```
输入#4
```
5 2
1 1 2 3 5
0 0 0 0 0
1 1
3 1
```
输出#4
```
4
```

说明/提示

小子任务

1.（8 分） $D_j = 0$ （ $1 \leq j \leq M$ ）。
2.（19 分） $B_i = 0$ （ $1 \leq i \leq N$ ）。
3.（31 分） $A_i = i$ （ $1 \leq i \leq N$ ）， $C_j = j$ （ $1 \leq j \leq M$ ）。
4.（42 分）无额外约束。

样例解释 1

合理分配蛋糕和红茶后，所有参与者幸福度总和最大为 $12$ 。

给参与者 $1$ 分配蛋糕 $1$ 与红茶 $1$ ，幸福度为 $2+3=5$ 。
给参与者 $2$ 分配蛋糕 $3$ 与红茶 $3$ ，幸福度为 $2+1=3$ 。
给参与者 $3$ 分配蛋糕 $4$ 与红茶 $2$ ，幸福度为 $4$ 。

无论如何分配，总幸福度不会超过 $12$ ，因此输出 $12$ 。

该输入样例满足小子任务 $4$ 的约束。

样例解释 2

该输入样例满足小子任务 $3, 4$ 的约束。

样例解释 3

该输入样例满足小子任务 $1, 4$ 的约束。

样例解释 4

该输入样例满足小子任务 $2, 4$ 的约束。

数据范围

$1 \leq M \leq N \leq 200\,000$ 。
$1 \leq A_i \leq N$ （ $1 \leq i \leq N$ ）。
$0 \leq B_i \leq 10^9$ （ $1 \leq i \leq N$ ）。
$1 \leq C_j \leq N$ （ $1 \leq j \leq M$ ）。
$0 \leq D_j \leq 10^9$ （ $1 \leq j \leq M$ ）。
所有输入值均为整数。

由 ChatGPT 5 翻译

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

首页