题目描述

作为一名现代企业家，你创办了一家生成式 AI 初创公司。图像、文本等内容的生成过程被拆分为 $N$ 个任务，每个任务在每个 GPU（图形处理器）上需要耗时一秒。你预先知道每个任务何时可用——任务 $i$ 在第 $T_i$ 秒可用。你拥有一个包含 $M$ 个 GPU 的外部超级计算机，但每个 GPU 每秒的使用成本不同——GPU $j$ 每秒的成本为 $C_j$。你需要为每个任务 $i$ 安排一个特定的 GPU $j$ 和一个特定的秒数，使得该秒数不早于 $T_i$，且同一时间同一 GPU 上不会安排其他任务。同样，一个 GPU 在给定的一秒内最多只能处理一个任务。

设最终完成时间（即最晚安排的时间加一）为 $F$，总支付金额为 $S$，即如果任务 $i$ 被安排在 GPU $G_i$ 上，则 $S = C_{G_1} + C_{G_2} + \dots + C_{G_N}$。

你需要找到 $F \times S$ 的最小值。你需要解决 $Q$ 个独立的、互不相关的任务实例。

输入格式

（注：本题为交互题，通过函数调用进行，具体见“交互”部分。）

数据范围

• $1 \le N \le 10^7$
• $1 \le M \le N$
• $0 \le T_i \le N$
• $1 \le C_j \le 2N$
• $1 \le Q \le 5$

交互

本题为交互题。你不需要从标准输入读取或向标准输出写入，只需编写一个具有以下签名的 solveGpus 函数：

__int128 solveGpus(
std::vector<int>& gpuCosts,
std::vector<int>& reqTimes);

函数接收的两个值向量将按非递减顺序排序。函数可以修改输入向量。函数返回 __int128 类型，这代表一个 128 位整数。这是必要的，因为答案可能超过 long long 的限制。该函数可能会被多次调用。每次调用都是一个独立的任务实例。

你的代码中不应包含 main 函数，但可以包含任何其他辅助函数、类、变量等。你的代码必须包含头文件 gpus.h，为了方便起见，该文件中还定义了 __int128 类型的输出运算符。这可以通过以下预处理指令实现：

#include "gpus.h"

你的代码将与一个读取输入并写入输出的评测器一起编译。在评测系统上，计入时间限制的唯一时间是你代码的执行时间，即输入和输出的时间不计入。

对于本地测试，我们提供了本地评测器 Lgrader.cpp 和 gpus.h 文件的副本。你需要将你的代码与本地评测器一起编译以进行测试。这可以通过将它们放在同一个文件夹中并使用以下命令完成：

g++ -O2 -std=c++17 -Wl,--stack,1073741824 -Wall gpus.cpp Lgrader.cpp
-o gpus.exe

子任务

只有当一个子任务的所有测试用例都通过时，才能获得该子任务的分数。

样例

样例遵循本地评测器的输入格式（$Q$，然后对于每个测试：$N, M$，所有 $C_j$，所有 $T_i$）。

输入 1

1
8 4
1 2 2 6
0 0 0 0 1 2 2 2

输出 1

39

说明 1

前 3 个任务在第 0 秒，接下来的 2 个任务在第 1 秒，最后 3 个任务在第 2 秒。 $S = 13$ $F = 3$