P16573 [USACO26Open] Haybale Stacks

**Note: The time limit for this problem is $2.5\text{s}$.** Farmer John has $N$ stacks of haybales ($1 \le N \le 5 \cdot 10^5$), where the $i\text{th}$ stack contains $a_i$ haybales ($1 \le a_i \le 10^9$). He wants to remove all of these haybales and has $M$ ($1 \le M \le 2500$) cows available to help him. If hired, the $i\text{th}$ cow will repeat the following $s_i$ times ($1 \le s_i \le 100$) for a cost of $c_i$ ($1 \le c_i \le 10^9$): - If the stack contains at least $p_i$ haybales ($1 \le p_i \le 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.

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, \ldots, 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\text{th}$ integer being the cost of removing all the haybales in the $i\text{th}$ stack.

First 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$. ### 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.