题目描述

作为一名现代创业者，你创办了一家生成式 AI 初创公司。

生成图像、文本等内容的过程被拆分为 $N$ 个任务，每个任务都需要 恰好 1 秒，并且在某一块 GPU（显卡）上执行。你事先知道每个任务何时变为可用：第 $i$ 个任务会在第 $T_i$ 秒可用。

你可以使用一台外部超级计算机，它有 $M$ 块 GPU，但每块 GPU 的单位时间使用价格不同：第 $j$ 块 GPU 每秒费用为 $C_j$。

你需要为每个任务 $i$ 安排：

• 一块具体的 GPU $j$；
• 一个具体的执行时刻（某一秒）。

要求满足：

• 该执行时刻不能早于 $T_i$；
• 同一块 GPU 在同一秒内不能执行多个任务；
• 每个任务恰好执行一次，耗时恰好为 1 秒。

设最终完成时间（即所有被安排的时刻中的最大值再加一）为 $F$。

设总费用为 $S$。如果任务 $i$ 被安排到 GPU $G_i$ 上，则：

$$S = C_{G_1} + C_{G_2} + \cdots + C_{G_N}$$

你需要求出 $F \times S$ 的最小可能值。

你将需要解决 $Q$ 组彼此独立的数据。

实现方式

本题为函数式提交题。

你不需要从标准输入读取，也不需要向标准输出写出答案，而是只需要实现下述函数：

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

其中：

• gpuCosts 表示所有 GPU 的使用费用，即数组 $C$；
• reqTimes 表示所有任务的最早可执行时间，即数组 $T$。

这两个数组在传入时都已经按照非降序排好序。

你的函数可以修改这两个输入数组。

函数返回值类型为 __int128，表示一个 128 位整数。这是必要的，因为答案可能超出 long long 的范围。

该函数可能会被调用多次，每次调用都是一组独立的测试数据。

代码要求

你的代码中不应包含 main 函数，但可以包含任意其他辅助函数、类、全局变量等。

你的代码需要包含头文件：

#include "gpus.h"

在 gpus.h 中，为了方便起见，也定义了 __int128 的输出运算符。

评测时，你的代码会与一个 grader 一起编译。grader 负责读入输入数据、调用你实现的函数并输出答案。

在评测系统中，只有你的代码运行时间会计入时间限制，输入输出时间不计入。

本地测试

官方提供了本地 grader：Lgrader.cpp，以及头文件副本 gpus.h。

你可以将自己的代码与本地 grader 放在同一目录下，并使用如下命令编译：

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

数据范围

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

子任务

子任务	分值	$N \le$	$Q \le$
1	10		1
2	8	800	2
3	13	2200
4	14	$10^4$
5	11	$10^5$
6	15	$10^6$	5
7	29	$10^7$

只有通过某个子任务的全部测试点，才能获得该子任务的分数。

样例

下面的样例遵循的是本地 grader 的输入格式：

• 第一行是 $Q$；
• 对于每组测试数据：
  • 输入 $N, M$；
  • 接着输入所有 $C_j$；
  • 再输入所有 $T_i$。

样例输入

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

样例输出

39

样例说明

一种最优安排方式是：

• 前 3 个任务安排在第 0 秒；
• 接下来的 2 个任务安排在第 1 秒；
• 最后的 3 个任务安排在第 2 秒。

此时：

$$S = 13$$ $$F = 3$$

因此答案为：

$$F \times S = 3 \times 13 = 39$$