Mana Collection
다이아몬드 III의견: 0
Note: The time limit for this problem is 5s, 2.5 times the default. The memory limit for this problem is 512MB, twice the default.
Bessie has recently taken an interest in magic and needs to collect mana for a
very important spell. Bessie has \(N\) (\(1\le N\le 18\)) mana pools, the \(i\)th of
which accumulates \(m_i\) mana per second (\(1\le m_i\le 10^8\)). The pools are
linked by a collection of \(M\) (\(0\le M\le N(N-1)\)) directed edges
\((a_i,b_i,t_i)\), meaning that she can travel from \(a_i\) to \(b_i\) in \(t_i\)
seconds (\(1\le a_i, b_i\le N\), \(a_i\neq b_i\), \(1\le t_i\le 10^9\)). Whenever
Bessie is present at a pool, she can collect all the mana stored at that
location, emptying it. At time \(0\), all mana pools are empty, and Bessie can
select any pool to start at.
Answer \(Q\) (\(1\le Q\le 2\cdot 10^5\)) queries, each specified by two integers \(s\)
and \(e\) (\(1\le s\le 10^9\), \(1\le e\le N\)). For each query, determine the maximum
amount of mana Bessie can collect in \(s\) seconds if she must be at mana pool \(e\)
at the end of the \(s\)th second.
Problem credits: Benjamin Qi
SCORING
- Inputs 3-4: \(N\le 10, Q\le 100\)
- Inputs 5-9: \(N\le 10\)
- Inputs 10-14: \(Q\le 100\)
- Inputs 15-17: \(N = 16\)
- Inputs 18-20: \(N = 17\)
- Inputs 21-24: No additional constraints.
Problem credits: Benjamin Qi
First line contains \(N\) and \(M\).
Next line contains \(m_1,m_2,\dots, m_N\).
Next \(M\) lines contain \(a_i,b_i,t_i\). No ordered pair \((a_i,b_i)\) appears more
than once in the input.
Next line contains \(Q\).
Next \(Q\) lines contain two integers \(s\) and \(e\).
\(Q\) lines, one for each query.
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
평가 및 의견
Mana Collection
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Mana Collection