P11049 [IOI 2024] Nile Transport

This is an interactive problem. You only need to implement the function required in the code. Your code must not include any additional header files, and you do not need to implement the `main` function. This problem only supports submissions in C++. However, please do not use C++14 (GCC 9).

You want to transport $N$ handicrafts through the Nile. These handicrafts are numbered from $0$ to $N-1$. The weight of handicraft $i$ ($0 \leq i < N$) is $W[i]$. To transport these handicrafts, you use special boats. Each boat can carry **at most** **two** handicrafts. - If you decide to put a single handicraft on a boat, its weight can be arbitrary. - If you want to put two handicrafts on the same boat, you must ensure the boat is balanced. Specifically, if handicrafts $p$ and $q$ ($0 \leq p < q < N$) have an absolute weight difference of at most $D$, i.e., $|W[p] - W[q]| \leq D$, then you may place them on the same boat. You must pay to transport a handicraft, and the cost depends on how many handicrafts are carried on the same boat. The transport cost for handicraft $i$ ($0 \leq i < N$) is: - $A[i]$, if you transport handicraft $i$ alone on a boat, or - $B[i]$, if you transport handicraft $i$ together with another handicraft. Note that in the second case, you pay the cost for both handicrafts on the boat. Specifically, if you decide to transport handicrafts $p$ and $q$ ($0 \leq p < q < N$) on the same boat, you need to pay $B[p] + B[q]$. The cost of transporting a handicraft alone on a boat is always higher than transporting it together with another handicraft, so for every $i$ satisfying $0 \leq i < N$, we have $B[i] < A[i]$. Unfortunately, because the Nile is unpredictable, the value of $D$ changes frequently. Your task is to answer $Q$ queries, numbered from $0$ to $Q-1$. The queries are described by an array $E$ of length $Q$. The answer to query $j$ ($0 \leq j < Q$) is the minimum total cost to transport all $N$ handicrafts when $D$ is equal to $E[j]$.

The grader reads the input data in the following order: ```plain N W[0] A[0] B[0] W[1] A[1] B[1] ... W[N-1] A[N-1] B[N-1] Q E[0] E[1] ... E[Q-1] ```

The grader outputs the following in order: ```plain R[0] R[1] ... R[S-1] ``` Here, $S$ is the length of the returned array $R$ from `calculate_costs`.

# Implementation Details You need to implement the following function. ``` std::vector calculate_costs( std::vector W, std::vector A, std::vector B, std::vector E) ``` - $W$, $A$, $B$: integer arrays of length $N$, giving the weights and costs of the handicrafts. - $E$: an integer array of length $Q$, giving the value of $D$ in each query. - The function should return an array $R$ containing $Q$ integers, giving the minimum total transport cost, where $R[j]$ corresponds to the cost when $D$ equals $E[j]$ (for each $j$ satisfying $0 \leq j < Q$). - For each test case, this function is called exactly once. # Constraints - $1 \leq N \leq 100\,000$. - $1 \leq Q \leq 100\,000$. - For each $i$ satisfying $0 \leq i < N$, $1 \leq W[i] \leq 10^{9}$. - For each $i$ satisfying $0 \leq i < N$, $1 \leq B[i] < A[i] \leq 10^{9}$. - For each $j$ satisfying $0 \leq j < Q$, $1 \leq E[j] \leq 10^{9}$. # Subtasks | Subtask | Points | Additional Constraints | | :-----: | :----: | ---------------------- | | 1 | $6$ | $Q \leq 5$; $N \leq 2000$; for each $i$ satisfying $0 \leq i < N$, $W[i] = 1$ | | 2 | $13$ | $Q \leq 5$; for each $i$ satisfying $0 \leq i < N$, $W[i] = i+1$ | | 3 | $17$ | $Q \leq 5$; for each $i$ satisfying $0 \leq i < N$, $A[i] = 2$ and $B[i] = 1$ | | 4 | $11$ | $Q \leq 5$; $N \leq 2000$ | | 5 | $20$ | $Q \leq 5$ | | 6 | $15$ | For each $i$ satisfying $0 \leq i < N$, $A[i] = 2$ and $B[i] = 1$ | | 7 | $18$ | No additional constraints. | # Hint Consider the following call. ``` calculate_costs([15, 12, 2, 10, 21], [5, 4, 5, 6, 3], [1, 2, 2, 3, 2], [5, 9, 1]) ``` In this example, we have $N=5$ handicrafts and $Q=3$ queries. In the first query, $D = 5$. You can put handicrafts $0$ and $3$ on the same boat (because $|15 - 10| \leq 5$), and put all other handicrafts on separate boats. This makes the minimum total cost to transport all handicrafts equal to $1+4+5+3+3 = 16$. In the second query, $D = 9$. You can put handicrafts $0$ and $1$ on the same boat (because $|15 - 12| \leq 9$), and put handicrafts $2$ and $3$ on the same boat (because $|2 - 10| \leq 9$). The remaining handicraft is transported alone on a boat. This makes the minimum total cost to transport all handicrafts equal to $1+2+2+3+3 = 11$. In the last query, $D = 1$. You need to transport each handicraft alone on a boat. This makes the minimum total cost to transport all handicrafts equal to $5+4+5+6+3 = 23$. Therefore, the function should return $[16, 11, 23]$. Translated by ChatGPT 5