← 返回题目列表

AtCoder · joisc2019_j

J. 蛋糕粘贴(蛋糕3)

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

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

ケーキの貼り合わせ (Cake 3) - 原题 PDF 第 1 页
原题PDF第1页
ケーキの貼り合わせ (Cake 3) - 原题 PDF 第 2 页
原题PDF第2页
ケーキの貼り合わせ (Cake 3) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                         Contest Day 4 – Cake 3

            ケーキの貼り合わせ(Cake 3)



 今日はIOI ちゃんの誕生日である.この日のためにJOI くんは誕生日ケーキを予約していたが,ホール

ケーキを予約したつもりが間違えてカットケーキを予約してしまっていた.JOI くんが購入したカットケー

キの個数はN である.カットケーキには1 からN までの番号が付けられていて,カットケーキi (1 ≦i ≦N)
の価値はVi,色の濃さはCi である.
 そこでJOI くんはこの中から異なるM 個のカットケーキを選び,好きな順に円状に並べ,貼り合わせて,
ホールケーキを作ることにした.カットケーキk1, . . . , kM をこの順に並べてできるホールケーキに対し,そ

の美しさが
             ∑M  ∑M
                                        Vk j −    Ck j −Ck j+1
                                                     j=1         j=1

で定義される(ただしkM+1 = k1 とする).つまり,美しさは,用いられるカットケーキの価値の合計から,
隣り合うカットケーキの色の濃さの差の絶対値の合計を引いた値となる.JOI くんはできるだけホールケー

キの美しさが大きくなるようにしたい.

 カットケーキの個数,各カットケーキの価値と色の濃さ,貼り合わせるカットケーキの個数が与えられた

とき,ホールケーキの美しさの最大値を求めるプログラムを作成せよ.


入力


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


    N M

      V1 C1
                                 ...

     VN CN


出力

 標準出力に,ホールケーキの美しさの最大値を1 行で出力せよ.





                   ケーキの貼り合わせ– 1 / 3

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                         Contest Day 4 – Cake 3



制約

    • 3 ≦N ≦200 000.

    • 3 ≦M ≦N.

    • 1 ≦Vi ≦1 000 000 000 (1 ≦i ≦N).
    • 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦N).


小課題

    1. (5 点) N ≦100.

    2. (19 点) N ≦2 000.

    3. (76 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   5 3                            6

   2 1

   4 2

   6 4

   8 8

   10 16

 カットケーキ1, 3, 2 を選び,この順に円状に並べて貼り合わせてホールケーキを作ると,価値の合計は

2 + 6 + 4 = 12 となり,隣り合うカットケーキの色の濃さの差の絶対値の合計は|1 −4| + |4 −2| + |2 −1| = 6

となる.ホールケーキの美しさは12 −6 = 6 である.

 カットケーキ2, 3, 4 を選び,この順に円状に並べて貼り合わせてホールケーキを作った場合も,ホール

ケーキの美しさは6 である.

 これより美しさの大きいホールケーキを作ることはできないので,6 を出力する.





                   ケーキの貼り合わせ– 2 / 3

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                      Spring Training Camp/Qualifying Trial

                                          March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                      Contest Day 4 – Cake 3


入力例2              出力例2

8 4                            2323231661

112103441 501365808

659752417 137957977

86280801 257419447

902409188 565237611

965602301 689654312

104535476 646977261

945132881 114821749

198700181 915994879





                 ケーキの貼り合わせ– 3 / 3