g6-02693. GESP-6级-2026-03-选数

题目描述

给定两个包含 $n$ 个整数的数组 $a = [a_{1}, \dots, a_{n}]$ 与 $b = [b_{1}, \dots, b_{n}]$ 。你需要指定若干下标 $p_{1} < \dots < p_{k}$ （ $1 \leq k \leq n$ ）使得以下条件成立：

你需要在满足以上条件的前提下最大化 $\sum_{i = 1}^{k} a_{p_{i}}$ ，也即最大化数组 $a$ 对应下标的整数之和。

第一行，一个正整数 $n$ ，表示数组长度。

第二行， $n$ 个正整数 $a_{1}, a_{2}, \dots, a_{n}$ ，表示数组 $a$ 。

第三行， $n$ 个正整数 $b_{1}, b_{2}, \dots, b_{n}$ ，表示数组 $b$ 。

一行，一个整数，表示在满足下标条件的前提下，数组 $a$ 对应下标的整数之和的最大值。

输入

4
1 2 3 4
3 3 1 1

输出

对于 $40%$ 的测试点，保证 $2 \leq n \leq 1 0^{3}$ 。

对于所有测试点，保证 $2 \leq n \leq 1 0^{5}$ ， $0 \leq a_{i} \leq 1 0^{9}$ ， $0 \leq b_{i} \leq n$ 。

来源：洛谷 P15800（CCF GESP 六级上机题）