P15843 [Bulgarian NOI 2024] Graphics Cards / GPUs

When submitting this problem on Luogu, please choose a language standard of >= C++17. You do not need to include `#include "gpus.h"`. Instead, explicitly place the following at the beginning of your code: ```cpp #include #include #include inline std::ostream& operator

As the founder of a modern startup company, you have launched a generative AI project. The generation process for images, text, etc. is split into $N$ tasks, and each task needs exactly one GPU (graphics card) to run for one second. You know in advance when each task becomes available—task $i$ becomes executable at second $T_i$. You can use an external supercomputer with $M$ GPUs, but the cost of using each GPU is different: GPU $j$ costs $C_j$ per second. You need to assign each task $i$ to a specific GPU $j$ and a specific time, such that the time is not earlier than $T_i$, and no other task is scheduled on the same GPU at the same moment. In other words, each GPU can process at most one task in any given second. Let the final completion time be $F$ (i.e., the latest scheduled time among all tasks plus one), and the total payment be $S$. If task $i$ is assigned to GPU $G_i$, then $S = C_{G_1} + C_{G_2} + \dots + C_{G_N}$. Your goal is to find the minimum possible value of $F \times S$. You need to solve $Q$ independent instances of this problem. ### Interaction Details This is an interactive problem. You do not need to read data from standard input or write data to standard output. You only need to implement a function named `solveGpus`, defined as follows: ```cpp __int128 solveGpus( std::vector& gpuCosts, std::vector& reqTimes ); ``` This function takes two vectors as parameters, and both vectors are sorted in **non-decreasing order**. You may modify the passed-in vectors. The return type is `__int128`, which represents a 128-bit integer—this is necessary because the answer may exceed the range of `long long`. This function will be called multiple times, and each call corresponds to an independent problem instance. Your code should not contain a `main` function, but it may contain any other helper functions, classes, variables, etc. Your code must include the header file `gpus.h`, which, for convenience, already defines the operator used to output values of type `__int128`. Please include this header via the following preprocessor directive: ```cpp #include "gpus.h" ``` Your code will be compiled together with the grader, which is responsible for reading input and writing output. In the judging system, the only time counted toward the time limit is the time your code actually spends executing; the time for input/output operations is not counted in the total time. For local testing, we provide a local grader `Lgrader.cpp` and a copy of the header file `gpus.h`. You need to compile your code together with the local grader for testing. You can place them in the same directory and use the following command: ```bash g++ -O2 -std=c++17 -Wl,--stack,1073741824 -Wall gpus.cpp Lgrader.cpp -o gpus.exe ```

The input format of the local grader is as follows: First comes $Q$, then for each test case: $N, M$, followed by all $C_j$ and all $T_i$.

N/A

### Subtasks | Subtask | Score | $N \le$ | $Q \le$ | |:------:|:----:|:-------:|:-------:| | $1$ | $10$ | $10$ | $1$ | | $2$ | $8$ | $800$ | $2$ | | $3$ | $13$ | $2200$ | $2$ | | $4$ | $14$ | $10^4$ | $2$ | | $5$ | $11$ | $10^5$ | $2$ | | $6$ | $15$ | $10^6$ | $5$ | | $7$ | $29$ | $10^7$ | $5$ | You will receive the score for a subtask only if you successfully pass all test points corresponding to that subtask. ### Constraints - $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$ Translation completed by Qwen3.5-397B-A17B. Translated by ChatGPT 5