Haybale Stacks
플래티넘 II의견: 0
*Note: The time limit for this problem is 2.5s.*
Farmer John has \(N\) stacks of haybales (\(1 \leq N \leq 5 \cdot 10^5\)), where the
\(i\)th stack contains \(a_i\) haybales (\(1 \leq a_i \leq 10^9\)). He wants to
remove all of these haybales and has \(M\) (\(1 \leq M \leq 2500\)) cows available
to help him. If hired, the \(i\)th cow will repeat the following \(s_i\) times
(\(1 \leq s_i \leq 100\)) for a cost of \(c_i\) (\(1 \leq c_i \leq 10^9\)):
- If the stack contains at least \(p_i\) haybales (\(1 \leq p_i \leq 10^9\)), then the cow will remove one haybale.
- If the stack contains less than \(p_i\) haybales, the cow does nothing.
For each stack, FJ wants to remove all of the haybales in it. He will do this by
hiring cows in sequence (possibly the same cow more than once) until the stack
becomes empty. Help FJ determine for each stack the minimum cost to empty it.
Problem credits: Sujay Konda
SCORING
- Inputs 2-3: \(a_i \le 100\)
- Inputs 4-5: \(\max(s)=1\)
- Inputs 6-9: \(\max(s)\le 4\)
- Inputs 10-15: \(\max(s)\le 20\)
- Inputs 16-21: No additional constraints.
Problem credits: Sujay Konda
The first line contains \(T\) (\(1\le T\le 100\)), the number of independent tests.
Each test is formatted as follows:
The first line contains an integer \(N\). The second line contains \(N\) integers,
\(a_1, a_2, \dots, a_N\).
The third line contains an integer \(M\). Then the next \(M\) lines will contain
\(p_i, s_i, c_i\).
It is guaranteed that the cows will be able to remove all the haybales in
every stack. Additionally, it is guaranteed that the sum of \(N\) over all tests
does not exceed \(5\cdot 10^5\), and the sum of \(M\) over all tests does not exceed
\(2500\).
For each test, print \(N\) space-separated integers, the \(i\)th integer being the
cost of removing all the haybales in the \(i\)th stack.
2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 329 155 21
73 328 50First test: For the last stack of initial size \(10\), we can hire cow \(3\) once,
which costs \(5\) and will remove haybales twice (not thrice because the number of
haybales turns to \(8\) after the second one is removed). Then we can hire cow \(2\)
twice, removing the \(8\) haybales, resulting in no haybales left. The total cost
is
\( 5+8+8=21\).
Second test: This satisfies \(\max(s)=1\).
평가 및 의견
Haybale Stacks
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Haybale Stacks