← 返回题目列表

Codeforces · 2073/F

F. 握住星星

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Hold the Star - 原题 PDF 第 1 页
原题PDF第11页
Hold the Star - 原题 PDF 第 2 页
原题PDF第12页
可复制的 PDF 提取文本
Problem F
                     Hold the Star
                     Time limit: 2 seconds


You are playing a computer game with n rooms, m characters, and one star. The rooms are arranged from left to right
and numbered from 1 to n in that order. The characters are numbered from 1 to m. At any time, each character is in
one of the rooms and the star is either in one of the rooms or held by one of the characters. The objective of the game
is for the star to be held by character m.

You can play the game by performing several actions. Each action costs a certain amount of staracips (the unit of
currency in the game), possibly zero. In each action, you choose a character x (let room y be the room the character is
currently in) and command the character to do either of the following:


     • Move to one of the adjacent rooms (y −1 or y + 1), if such a room exists. If character x is holding the star, then
      the character continues to hold the star. This action costs sx staracips. The values of s1, s2, . . . , sm are given.

     • Pick the star up and hold it, if the star is currently in room y and is not held by any character. This action costs
     0 staracips.

     • Put the star down and release it, if the star is currently held by character x. The star then falls to room y. This
      action costs 0 staracips.


The game contains q levels, numbered from 1 to q. In all levels, each character i is initially in room ri and character m
must hold the star to win the level. The only difference between the levels is that, in each level j, the star is initially in
room lj.

For each level, you want to compute the minimum total staracips you have to spend to win the level. Note that you
don’t have to minimize the number of actions.

Input
The first line of input contains three integers n, m, and q (1 ≤n ≤109; 1 ≤m ≤100 000; 1 ≤q ≤100 000). The
i-th of the next m lines contains two integers ri and si (1 ≤ri ≤n; 1 ≤si ≤109). The j-th of the next q lines
contains an integer lj (1 ≤lj ≤n).

Output

For each level in order, output the minimum total staracips you have to spend to win the level.





The 2025 ICPC Asia Pacific Championship Problem F: Hold the Star

Sample Input #1                          Sample Output #1
 6 5 4                                  5
 1 7                                    0
 3 2                                    8
 2 3                                    14
 5 3
 2 5
 1
 2
 5
 6


Explanation for the sample input/output #1

You can win the first level by spending 5 staracips by doing the following actions:

   1. Character 5 moves from room 2 to room 1. This action costs 5 staracips.

   2. Character 5 picks the star up.

You can win the second level by spending 0 staracips by doing the following actions:

   1. Character 5 picks the star up.

You can win the third level by spending 8 staracips by doing the following actions:

   1. Character 4 picks the star up.

   2. Character 4 moves from room 5 to room 4. This action costs 3 staracips.

   3. Character 4 moves from room 4 to room 3. This action costs 3 staracips.

   4. Character 4 puts the star down.

   5. Character 2 picks the star up.

   6. Character 2 moves from room 3 to room 2. This action costs 2 staracips.

   7. Character 2 puts the star down.

   8. Character 5 picks the star up.

You can win the fourth level by spending 14 staracips by doing the following actions:

   1. Character 2 moves from room 3 to room 4, then to room 5, then to room 6. These actions cost 3 × 2 = 6
      staracips in total.

   2. Character 2 picks the star up.

   3. Character 2 moves from room 6 to room 5, then to room 4, then to room 3, then to room 2. These actions cost
     4 × 2 = 8 staracips in total.

   4. Character 2 puts the star down.

   5. Character 5 picks the star up.


The 2025 ICPC Asia Pacific Championship Problem F: Hold the Star