레이팅 미적용*참고: 이 문제의 시간 제한은 2.5초이다.*
농부 존은 \(N\)개의 건초 더미 스택 (\(1 \leq N \leq 5 \cdot 10^5\))을 가지고 있으며, \(i\)번째 스택에는 \(a_i\)개의 건초 더미가 있다 (\(1 \leq a_i \leq 10^9\)). 그는 이 건초 더미를 모두 치우고 싶으며, 그를 도와줄 수 있는 \(M\) (\(1 \leq M \leq 2500\))마리의 소가 있다. \(i\)번째 소는 고용되면 비용 \(c_i\) (\(1 \leq c_i \leq 10^9\))를 받고 다음을 \(s_i\)번 (\(1 \leq s_i \leq 100\)) 반복한다.
- 스택에 건초 더미가 \(p_i\)개 이상 있으면 (\(1 \leq p_i \leq 10^9\)), 소는 건초 더미 하나를 치운다.
- 스택에 건초 더미가 \(p_i\)개 미만이면, 소는 아무것도 하지 않는다.
농부 존은 각 스택마다 그 안의 건초 더미를 모두 치우고 싶다. 그는 스택이 빌 때까지 소를 차례로(같은 소를 여러 번 고용할 수도 있다) 고용하여 이를 수행할 것이다. 각 스택에 대해 그것을 비우는 최소 비용을 구하는 것을 도와주자.
문제 제공: Sujay Konda
채점 방식
- 입력 2-3: \(a_i \le 100\)
- 입력 4-5: \(\max(s)=1\)
- 입력 6-9: \(\max(s)\le 4\)
- 입력 10-15: \(\max(s)\le 20\)
- 입력 16-21: 추가 제약 조건이 없다.
문제 제공: Sujay Konda
첫째 줄에 독립적인 테스트의 수 \(T\) (\(1\le T\le 100\))가 주어진다. 각 테스트는 다음 형식으로 주어진다.
첫째 줄에 정수 \(N\)이 주어진다. 둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \dots, a_N\)이 주어진다.
셋째 줄에 정수 \(M\)이 주어진다. 그다음 \(M\)개의 줄에 \(p_i, s_i, c_i\)가 주어진다.
소들이 모든 스택의 건초 더미를 전부 치울 수 있음이 보장된다. 추가로, 모든 테스트에 대한 \(N\)의 합은 \(5\cdot 10^5\)를 넘지 않고, \(M\)의 합은 \(2500\)을 넘지 않음이 보장된다.
각 테스트마다 \(N\)개의 정수를 공백으로 구분하여 출력한다. \(i\)번째 정수는 \(i\)번째 스택의 건초 더미를 모두 치우는 비용이다.
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\).