以下是来自日本的原始新闻PDF,已完整保存和染色。



可复制的 PDF 提取文本
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Relay
リレー競技(Relay)
JOI 高校の陸上部にはN 人の部員がおり,1 からN までの番号が付けられている.部員i (1 ≦i ≦N) の
100 m 走のタイムはAi ミリ秒であり,バトンパスの速さはBi である.
さて,この陸上部は300 m リレーの全国大会に出場することになった.300 m リレーは,3 人の走者がバ
トンを渡しながら100 m ずつ走る競技である.具体的には,第1 走者が部員i (1 ≦i ≦N),第2 走者が部員
j (1 ≦j ≦N),第3 走者が部員k (1 ≦k ≦N) であるとき,以下の手順で行われる.
1. 部員i がバトンを持って100 m 走る.これにはAi ミリ秒かかる.
2. 部員i から部員j にバトンを渡す.これにはmax(Bi, Bj) ミリ秒かかる.
3. 部員j がバトンを持って100 m 走る.これにはAj ミリ秒かかる.
4. 部員j から部員k にバトンを渡す.これにはmax(Bj, Bk) ミリ秒かかる.
5. 部員k がバトンを持って100 m 走る.これにはAk ミリ秒かかる.
すなわち,300m リレーの記録はAi +max(Bi, Bj)+A j +max(Bj, Bk)+Ak ミリ秒となる.ここで,max(x, y)
はx とy のうち小さくない方の数とする.あなたは陸上部の顧問であるため,この記録ができるだけ短くな
るように3 人の異なる部員を選び,その走順を決めなければならない.
陸上部のN 人の部員の情報が与えられたとき,300 m リレーの記録として考えられる最小値を求めるプ
ログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
A1 B1
A2 B2
...
AN BN
出力
標準出力に,300 m リレーの記録として考えられる最小値をミリ秒単位で表す整数を1 行で出力せよ.
リレー競技– 1 / 3
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Relay
制約
• 3 ≦N ≦200 000.
• 1 ≦Ai ≦100 000 000 (= 108) (1 ≦i ≦N).
• 1 ≦Bi ≦100 000 000 (= 108) (1 ≦i ≦N).
小課題
1. (25 点) N ≦100.
2. (33 点) N ≦3 000.
3. (10 点) A1 = A2 = · · · = AN.
4. (32 点) 追加の制約はない.
入出力例
入力例1 出力例1
4 3320
1070 90
1080 70
1050 60
1020 100
第1 走者に部員4,第2 走者に部員3,第3 走者に部員2 を選ぶと,手順1, 2, 3, 4, 5 にはそれぞれ
1020, 100, 1050, 70, 1080 ミリ秒かかるため,300 m リレーの記録は1020 + 100 + 1050 + 70 + 1080 = 3320
ミリ秒となる.これより記録を短くすることはできないため,3320 を出力する.
この入力例は小課題1, 2, 4 の制約を満たす.
入力例2 出力例2
5 3034
1000 28
1000 14
1000 21
1000 20
1000 14
リレー競技– 2 / 3
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Relay
第1 走者に部員2,第2 走者に部員5,第3 走者に部員4 を選ぶと,手順1, 2, 3, 4, 5 にはそれぞれ
1000, 14, 1000, 20, 1000 ミリ秒かかるため,300 m リレーの記録は1000 + 14 + 1000 + 20 + 1000 = 3034 ミ
リ秒となる.これより記録を短くすることはできないため,3034 を出力する.
この入力例はすべての小課題の制約を満たす.
入力例3 出力例3
9 13
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3
第1 走者に部員1,第2 走者に部員2,第3 走者に部員9 を選ぶと,手順1, 2, 3, 4, 5 にはそれぞれ
3, 1, 4, 3, 2 ミリ秒かかるため,300 m リレーの記録は3 + 1 + 4 + 3 + 2 = 13 ミリ秒となる.これより記録を
短くすることはできないため,13 を出力する.
この入力例は小課題1, 2, 4 の制約を満たす.
リレー競技– 3 / 3