[USACO23JAN] Mana Collection P

Luogu

IDLGP9020

Time5000ms

Memory512MB

DifficultyP6

USACO2023凸包李超线段树状压 DP

**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 ith 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. ## Input First line contains $N$ and $M$. Next line contains $m_1,m2, \cdots ,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$. ## Output $Q$ lines, one for each query. [samples] ## Note ### Explanation for Sample 1 First 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. ### Explanation for Sample 2 An example where Bessie is able to collect much larger amounts of mana. ### 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.

Samples

Input #1

Output #1

Input #2

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 4

Output #2

160000000
239999988050000000
119992550000000

API Response (JSON)

{
  "problem": {
    "name": "[USACO23JAN] Mana Collection P",
    "description": {
      "content": "**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 coll",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9020"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**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.**\n\nBessie has recently taken an interest in magic and needs to coll...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments