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



可复制的 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