← 返回题目列表

AtCoder · joisc2021_i

H. 保镖

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

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

ボディーガード (Bodyguard) - 原题 PDF 第 1 页
原题PDF第1页
ボディーガード (Bodyguard) - 原题 PDF 第 2 页
原题PDF第2页
ボディーガード (Bodyguard) - 原题 PDF 第 3 页
原题PDF第3页
ボディーガード (Bodyguard) - 原题 PDF 第 4 页
原始 PDF 第 4 部分
ボディーガード (Bodyguard) - 原题 PDF 第 5 页
原题PDF第5页
可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                      Contest Day 3 – Bodyguard

              ボディーガード(Bodyguard)



  JOI 通りは東西に広がる長い道であり,数直線とみなすことが出来る.

 これからN 人の要人がJOI 通りを移動する.要人には1 からN までの番号が付けられている.要人i
(1 ≦i ≦N) は時刻Ti に座標Ai を出発し,速さ1 (単位時間あたりに座標を1 移動する速さ) で座標Bi まで
移動する.Ai < Bi ならば正の方向,Ai > Bi ならば負の方向に,常に等速で移動することを意味している.
 ボディーガードの仕事は,JOI 通りを移動して,これらの要人を警護することである.要人の警護とは,

ある時刻からある時刻まで,要人と一緒に移動することを指す.ある要人の移動の途中から警護を始めても

よいし,要人の移動が完了する前に警護をやめてもよい.警護の開始と終了の時刻は整数である必要はな

い.ただし,2 人以上の要人が同じ座標に存在する時間があっても,同時に警護できるのは1 人までである.

 ボディーガードは常に速さ1 以下で自由にJOI 通りを移動することが出来る.ある要人の警護を終了し

た後,移動して他の要人を警護することも出来る.要人i の警護をすると,一緒に移動した距離に応じて,
距離1 あたりCi 円の報酬が得られる.Ci は偶数であることが保証される.
 警備会社に勤務するあなたは,要人を警護するQ 個の計画を検討することにした.計画には1 からQ ま
での番号が付けられている.計画j (1 ≦j ≦Q) では,1 人のボディーガードが時刻Pj に座標Xj から仕事

を開始する.あなたは,それぞれの計画について,得られる報酬をできるだけ大きくしたい.

 要人と計画の情報が与えられたとき,それぞれの計画について得られる報酬の最大値を求めるプログラム

を作成せよ.

 この問題の制約の下では,得られる報酬の最大値は必ず整数になることが証明できる.


入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N Q

      T1 A1 B1 C1
                                 ...

     TN AN BN CN
      P1 X1
                                 ...

     PQ XQ





                    ボディーガード– 1 / 5

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                      Contest Day 3 – Bodyguard



出力

 標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) には計画j において得られる報酬の最大値を整数で出力

せよ.


制約

    • 1 ≦N ≦2 800.

    • 1 ≦Q ≦3 000 000.
    • 1 ≦Ti ≦1 000 000 000 (1 ≦i ≦N).
    • 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦N).
    • 1 ≦Bi ≦1 000 000 000 (1 ≦i ≦N).
    • Ai , Bi (1 ≦i ≦N).
    • 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦N).
    • Ci は偶数(1 ≦i ≦N).
    • 1 ≦P j ≦1 000 000 000 (1 ≦j ≦Q).
    • 1 ≦X j ≦1 000 000 000 (1 ≦j ≦Q).


小課題

    1. (6 点) Ti ≦3 000,Ai ≦3 000,Bi ≦3 000 (1 ≦i ≦N).Pj ≦3 000,X j ≦3 000 (1 ≦j ≦Q).
    2. (7 点) Q = 1.

    3. (15 点) Q ≦3 000.

    4. (20 点) Q ≦40 000.

    5. (52 点) 追加の制約はない.





                    ボディーガード– 2 / 5

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                      Contest Day 3 – Bodyguard



入出力例

  入力例1              出力例1

   2 2                            8

   1 2 1 4                        2

   3 1 3 2

   1 2

   3 3

 計画1 では,以下の通りに行動することで,4 + 4 = 8 円の報酬を得る.

    1. ボディーガードは時刻1 に座標2 から仕事を開始する.

    2. 時刻1 から時刻2 まで,要人1 を警護する.距離1 を移動したため,報酬として4 × 1 = 4 円を得る.

    3. 時刻2 から時刻3 まで,座標1 で留まる.

    4. 時刻3 から時刻5 まで,要人2 を警護する.距離2 を移動したため,報酬として2 × 2 = 4 円を得る.

これより多くの報酬を得ることは不可能であるため,1 行目に8 を出力する.


 計画2 では,以下の通りに行動することで,2 円の報酬を得る.

    1. ボディーガードは時刻3 に座標3 から仕事を開始する.

    2. 時刻3 から時刻4 までかけて,座標3 から座標2 に移動する.

    3. 時刻4 から時刻5 まで,要人2 を警護する.距離1 を移動したため,報酬として2 × 1 = 2 円を得る.

これより多くの報酬を得ることは不可能であるため,2 行目に2 を出力する.


 この入力例は小課題1, 3, 4, 5 の制約を満たす.





                    ボディーガード– 3 / 5

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                      Contest Day 3 – Bodyguard


  入力例2              出力例2

   3 2                            15

   3 1 5 2                        0

   1 4 1 4

   4 2 4 4

   2 2

   6 3

 計画1 では,以下の通りに行動することで,4 + 1 + 8 + 2 = 15 円の報酬を得る.

    1. ボディーガードは時刻2 に座標2 から仕事を開始する.

    2. 時刻2 から時刻2.5 までかけて,座標2 から座標2.5 に移動する.

    3. 時刻2.5 から時刻3.5 まで,要人2 を警護する.距離1 を移動したため,報酬として4 × 1 = 4 円を

   得る.

    4. 時刻3.5 から時刻4 まで,要人1 を警護する.距離0.5 を移動したため,報酬として2 × 0.5 = 1 円

   を得る.

    5. 時刻4 から時刻6 まで,要人3 を警護する.距離2 を移動したため,報酬として4 × 2 = 8 円を得る.

    6. 時刻6 から時刻7 まで,要人1 を警護する.距離1 を移動したため,報酬として2 × 1 = 2 円を得る.

これより多くの報酬を得ることは不可能であるため,1 行目に15 を出力する.


 計画2 では,ボディーガードは時刻6 に座標3 から仕事を開始する.しかし,要人を警護することはで

きない.したがって報酬の最大値は0 円であり,2 行目に0 を出力する.


 この入力例は小課題1, 3, 4, 5 の制約を満たす.





                    ボディーガード– 4 / 5

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2021 (Komaba, Tokyo)


                                                                    Contest Day 3 – Bodyguard


 入力例3              出力例3

 5 5                            30

 8 1 4 10                       27

 8 3 7 6                        48

 1 4 6 2                        30

 3 9 5 4                        48

 6 1 9 6

 7 6

 6 8

 1 3

 9 4

 2 4

この入力例は小課題1, 3, 4, 5 の制約を満たす.





                   ボディーガード– 5 / 5