AdditionalFile4286.zip

#4286. 「KTSC 2021 R2」猴子

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "monkey.h"。

题目描述

题目译自 2021년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T3 「원숭이」

有两根柱子 A 和 B 并排放置。每根柱子上有 $N$ 个把手，从下到上依次编号为 $1$ 到 $N$。每个把手上可能挂有 $0$ 个或更多的香蕉。$A_{i}$ 表示柱子 A 的第 $i$ 个把手上挂着的香蕉数量，$B_{j}$ 表示柱子 B 的第 $j$ 个把手上挂着的香蕉数量。这些值都是 $0$ 到 $10^{9}$ 之间的整数。

猴子可以用两只手分别抓住不同柱子上的把手。注意，猴子不能同时抓住同一根柱子上的两个把手。此外，猴子不能随意抓住任何把手。猴子可以抓住的把手对用 $(x, y)$ 表示，表示猴子可以同时抓住柱子 A 的第 $x$ 个把手和柱子 B 的第 $y$ 个把手。在这种情况下，猴子可以吃掉这两个把手上的所有香蕉。显然，吃掉的香蕉不会再出现。这样的把手对总共有 $M$ 个。

最初，猴子从可以抓住的把手对中的一个位置开始。如果猴子当前在 $(x, y)$ 位置，要移动到另一个可以抓住的把手对 $\left(x^{\prime}, y^{\prime}\right)$，必须满足 $x<x^{\prime}, y=y^{\prime}$ 或 $x=x^{\prime}, y<y^{\prime}$。

猴子当然想吃到尽可能多的香蕉。给定可以抓住的把手对的信息以及这些把手上挂着的香蕉数量的信息，编写一个程序，计算猴子最多可以吃到多少香蕉。

实现细节

你需要实现以下函数：

long long int max_bananas(vector<int> A, vector<int> B, vector< pair<int, int> > P);

• 该函数只会被调用一次。
• 参数 A 的长度为 $N$，A[i] $(0 \leq i \leq N-1)$ 表示柱子 A 的第 $i+1$ 个把手上挂着的香蕉数量。
• 参数 B 的长度为 $N$，B[i] $(0 \leq i \leq N-1)$ 表示柱子 B 的第 $i+1$ 个把手上挂着的香蕉数量。
• 参数 P 的长度为 $M$，如果 $(x, y)$ 包含在 P 中，表示猴子可以同时抓住柱子 A 的第 $x$ 个把手和柱子 B 的第 $y$ 个把手，并吃掉这两个把手上的所有香蕉。保证不会有重复的把手对。
• 该函数返回猴子最多可以吃到的香蕉数量。

注意，提交的代码中不应包含任何输入输出操作。

样例

考虑 $N=3, M=3, A=[2,3,1], B=[3,2,4], P=[(1,1),(2,1),(1,3)]$ 的情况，如图所示。

评测程序将调用如下函数：

max_bananas([2,3,1],[3,2,4],[(1,1),(2,1),(1,3)]);

从 $(1,1)$ 位置开始，移动到 $(1,3)$ 位置，总共可以吃到 $2+3+4=9$ 个香蕉，没有比这更多的吃法。因此，max_bananas 函数应返回 9。

这个示例满足所有子任务的条件。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 5\cdot 10^5$
• $1 \leq M \leq 5\cdot 10^5$
• $M \leq N^{2}$
• $0 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
• $0 \leq B_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
• 参数 P 中的把手对 $(x, y)$ 都是不同的，且满足 $1 \leq x \leq N, 1 \leq y \leq N$。

详细子任务附加限制及分值如下表所示。

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N\,M$
• 第 $2$ 行：$A[0]\,A[1]\,\cdots\,A[N-1]$
• 第 $3$ 行：$B[0]\,B[1]\,\cdots\,B[N-1]$
• 第 $3+i$ $(1 \leq i \leq M)$ 行：$P[i-1].\text{first}\,P[i-1].\text{second}$

示例评测程序按以下格式输出：

• 第 $1$ 行：函数 max_bananas 返回的值

示例评测程序可能与实际评测程序不同。