32266번 - Nile 서브태스크다국어언어 제한함수 구현

문제

You want to transport $N$ artifacts through the Nile. The artifacts are numbered from 0ドル$ to $N - 1$. The weight of artifact $i$ (0ドル ≤ i < N$) is $W[i]$.

To transport the artifacts, you use specialized boats. Each boat can carry at most two artifacts.

• If you decide to put a single artifact in a boat, the artifact weight can be arbitrary.
• If you want to put two artifacts in the same boat, you have to make sure the boat is balanced evenly. Specifically, you can send artifacts $p$ and $q$ (0ドル ≤ p < q < N$) in the same boat only if the absolute difference between their weights is at most $D,ドル that is $|W[p] - W[q]| ≤ D$.

To transport an artifact, you have to pay a cost that depends on the number of artifacts carried in the same boat. The cost of transporting artifact $i$ (0ドル ≤ i < N$) is:

• $A[i],ドル if you put the artifact in its own boat, or
• $B[i],ドル if you put it in a boat together with some other artifact.

Note that in the latter case, you have to pay for both artifacts in the boat. Specifically, if you decide to send artifacts $p$ and $q$ (0ドル ≤ p < q < N$) in the same boat, you need to pay $B[p] + B[q]$.

Sending an artifact in a boat by itself is always more expensive than sending it with some other artifact sharing the boat with it, so $B[i] < A[i]$ for all $i$ such that 0ドル ≤ i < N$.

Unfortunately, the river is very unpredictable and the value of $D$ changes often. Your task is to answer $Q$ questions numbered from 0ドル$ to $Q - 1$. The questions are described by an array $E$ of length $Q$. The answer to question $j$ (0ドル ≤ j < Q$) is the minimum total cost of transporting all $N$ artifacts, when the value of $D$ is equal to $E[j]$.

구현 상세

You should implement the following procedure.

std::vector<long long> calculate_costs(
 std::vector<int> W, std::vector<int> A,
 std::vector<int> B, std::vector<int> E)

• $W,ドル $A,ドル $B$: arrays of integers of length $N,ドル describing the weights of the artifacts and the costs of transporting them.
• $E$: an array of integers of length $Q$ describing the value of $D$ for each question.
• This procedure should return an array $R$ of $Q$ integers containing the minimum total cost of transporting the artifacts, where $R[j]$ gives the cost when the value of $D$ is $E[j]$ (for each $j$ such that 0ドル ≤ j < Q$).
• This procedure is called exactly once for each test case.

입력

출력

제한

• 1ドル ≤ N ≤ 100,円 000$
• 1ドル ≤ Q ≤ 100,円 000$
• 1ドル ≤ W[i] ≤ 10^9$ for each $i$ such that 0ドル ≤ i < N$
• 1ドル ≤ B[i] < A[i] ≤ 10^9$ for each $i$ such that 0ドル ≤ i < N$
• 1ドル ≤ E[j] ≤ 10^9$ for each $j$ such that 0ドル ≤ j < Q$

서브태스크

힌트

예제

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$ artifacts and $Q = 3$ questions.

In the first question, $D = 5$. You can send artifacts 0ドル$ and 3ドル$ in one boat (since $|15 - 10| ≤ 5$) and the remaining artifacts in separate boats. This yields the minimum cost of transporting all the artifacts, which is 1ドル + 4 +たす 5 +たす 3 +たす 3 =わ 16$.

In the second question, $D = 9$. You can send artifacts 0ドル$ and 1ドル$ in one boat (since $|15 - 12| ≤ 9$) and send artifacts 2ドル$ and 3ドル$ in one boat (since $|2 - 10| ≤ 9$). The remaining artifact can be sent in a separate boat. This yields the minimum cost of transporting all the artifacts, which is 1ドル + 2 +たす 2 +たす 3 +たす 3 =わ 11$.

In the final question, $D = 1$. You need to send each artifact in its own boat. This yields the minimum cost of transporting all the artifacts, which is 5ドル + 4 +たす 5 +たす 6 +たす 3 =わ 23$.

Hence, this procedure should return $[16, 11, 23]$.

샘플 그레이더

Input format:

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]

Output format:

R[0]
R[1]
...
R[S-1]

Here, $S$ is the length of the array $R$ returned by calculate_costs.

첨부

• nile.zip