레이팅 미적용참고: 이 문제의 시간 제한은 기본의 2.5배인 5초이다. 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.
베시는 최근 마법에 흥미가 생겨 매우 중요한 주문을 위해 마나를 모아야 한다. 베시에게는 \(N\) (\(1\le N\le 18\))개의 마나 웅덩이가 있고, \(i\)번째 웅덩이에는 초당 \(m_i\) (\(1\le m_i\le 10^8\))의 마나가 쌓인다. 웅덩이들은 \(M\) (\(0\le M\le N(N-1)\))개의 방향 간선 \((a_i,b_i,t_i)\)로 연결되어 있으며, 이는 \(a_i\)에서 \(b_i\)까지 \(t_i\)초에 이동할 수 있음을 의미한다 (\(1\le a_i, b_i\le N\), \(a_i\neq b_i\), \(1\le t_i\le 10^9\)). 베시는 웅덩이에 있을 때마다 그곳에 쌓인 마나를 모두 수집하여 웅덩이를 비울 수 있다. 시각 \(0\)에 모든 마나 웅덩이는 비어 있고, 베시는 아무 웅덩이나 골라 출발할 수 있다.
\(Q\) (\(1\le Q\le 2\cdot 10^5\))개의 쿼리에 답해야 하며, 각 쿼리는 두 정수 \(s\)와 \(e\) (\(1\le s\le 10^9\), \(1\le e\le N\))로 지정된다. 각 쿼리에 대해, \(s\)번째 초가 끝나는 시점에 마나 웅덩이 \(e\)에 있어야 할 때 베시가 \(s\)초 동안 모을 수 있는 마나의 최대량을 구한다.
출제자: Benjamin Qi
배점
- 입력 3-4: \(N\le 10, Q\le 100\)
- 입력 5-9: \(N\le 10\)
- 입력 10-14: \(Q\le 100\)
- 입력 15-17: \(N = 16\)
- 입력 18-20: \(N = 17\)
- 입력 21-24: 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 줄에 \(m_1,m_2,\dots, m_N\)이 주어진다.
다음 \(M\)개의 줄에 \(a_i,b_i,t_i\)가 주어진다. 순서쌍 \((a_i,b_i)\)는 입력에서 두 번 이상 등장하지 않는다.
다음 줄에 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 두 정수 \(s\)와 \(e\)가 주어진다.
각 쿼리마다 한 줄씩, 총 \(Q\)개의 줄을 출력한다.
2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 25
50
100
1090First query: Bessie takes 5 mana from pool 1 after 5 seconds.
Second query: Bessie takes 50 mana from pool 2 after 5 seconds.
Third query: Bessie takes 100 mana from pool 1 after 100 seconds.
Fourth query: Bessie takes 90 mana from pool 1 after 90 seconds and 1000 mana
from pool 2 after 100 seconds.
4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4160000000
239999988050000000
119992550000000An example where Bessie is able to collect much larger amounts of mana.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Platinum