以下是来自日本的官方新闻原版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 2 – Two Dishes
ふたつの料理(Two Dishes)
料理人のビ太郎は,料理コンテストに出ることにした.このコンテストでは,2 つの料理を作る必要があ
る.作る料理はIOI 丼とJOI カレーである.
IOI 丼の作り方はN 個の手順に分かれていて,i 番目(1 ≦i ≦N) の手順を行うのにちょうどAi 分かかる.
はじめ,行うことのできる手順は1 番目の手順のみである.i 番目(2 ≦i ≦N) の手順を行うためには,i −1
番目の手順が完了している必要がある.
JOI カレーの作り方はM 個の手順に分かれていて,j 番目(1 ≦j ≦M) の手順を行うのにちょうどBj 分
かかる.はじめ,行うことのできる手順は1 番目の手順のみである.j 番目(2 ≦j ≦M) の手順を行うため
には,j −1 番目の手順が完了している必要がある.
手順は集中力を必要とするため,ある手順を始めたら,その手順が終わるまでは他の手順を行うことはで
きない.手順と手順の間では,作業する料理を切り替えてもよい.また,コンテストが開始したら,2 つの
料理が完成するまで休むことはできない.
さて,このコンテストには芸術点というものが存在する.芸術点は次のように与えられる.
• IOI 丼のi 番目(1 ≦i ≦N) の手順をコンテスト開始からS i 分以内に完了すると,Pi 点が与えられ
る.ただし,Pi の値は負かもしれない.
• JOI カレーのj 番目(1 ≦j ≦M) の手順をコンテスト開始からT j 分以内に完了すると,Q j 点が与え
られる.ただし,Q j の値は負かもしれない.
ビ太郎は得られる芸術点の合計を最大化したい.
料理の手順の個数,それぞれの手順にかかる時間,芸術点の採点情報が与えられたとき,得られる芸術点
の最大値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.
N M
A1 S 1 P1
...
AN S N PN
B1 T1 Q1
...
BM TM QM
ふたつの料理– 1 / 5
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Two Dishes
出力
標準出力に,ビ太郎が得ることのできる芸術点の合計の最大値を1 行で出力せよ.
制約
• 1 ≦N ≦1 000 000.
• 1 ≦M ≦1 000 000.
• 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦Bj ≦1 000 000 000 (1 ≦j ≦M).
• 1 ≦S i ≦2 000 000 000 000 000 = 2 × 1015 (1 ≦i ≦N).
• 1 ≦T j ≦2 000 000 000 000 000 = 2 × 1015 (1 ≦j ≦M).
• −1 000 000 000 ≦Pi ≦1 000 000 000 (1 ≦i ≦N).
• −1 000 000 000 ≦Q j ≦1 000 000 000 (1 ≦j ≦M).
小課題
1. (5 点) N ≦200 000,M ≦200 000,S 1 = · · · = S N = T1 = · · · = TM,1 ≦Pi (1 ≦i ≦N),1 ≦Q j
(1 ≦j ≦M).
2. (3 点) N ≦12,M ≦12,Pi = 1 (1 ≦i ≦N),Q j = 1 (1 ≦j ≦M).
3. (7 点) N ≦2 000,M ≦2 000,Pi = 1 (1 ≦i ≦N),Q j = 1 (1 ≦j ≦M).
4. (39 点) N ≦200 000,M ≦200 000,Pi = 1 (1 ≦i ≦N),Q j = 1 (1 ≦j ≦M).
5. (11 点) N ≦200 000,M ≦200 000,1 ≦Pi (1 ≦i ≦N),1 ≦Q j (1 ≦j ≦M).
6. (9 点) 1 ≦Pi (1 ≦i ≦N),1 ≦Q j (1 ≦j ≦M).
7. (17 点) N ≦200 000,M ≦200 000.
8. (9 点) 追加の制約はない.
ふたつの料理– 2 / 5
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Two Dishes
入出力例
入力例1 出力例1
4 3 6
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1
この入力例は小課題2 の制約を満たす.
この入力例において,例えば次のような順番ですべての手順をこなしていくとする.
1. JOI カレーの1 番目の手順を行う.手順が完了したとき経過時間はコンテスト開始から3 分である.
6 分以内なので1 点を得る.
2. IOI 丼の1 番目の手順を行う.手順が完了したとき経過時間はコンテスト開始から5 分である.1 分
以内ではないので芸術点は得られない.
3. IOI 丼の2 番目の手順を行う.手順が完了したとき経過時間はコンテスト開始から8 分である.8 分
以内なので1 点を得る.
4. JOI カレーの2 番目の手順を行う.手順が完了したとき経過時間はコンテスト開始から10 分である.
11 分以内なので1 点を得る.
5. IOI 丼の3 番目の手順を行う.手順が完了したとき経過時間はコンテスト開始から12 分である.13
分以内なので1 点を得る.
6. IOI 丼の4 番目の手順を行う.手順が完了したとき経過時間はコンテスト開始から13 分である.13
分以内なので1 点を得る.
7. JOI カレーの3 番目の手順を行う.手順が完了したとき経過時間はコンテスト開始から15 分である.
15 分以内なので1 点を得る.
このとき,芸術点の合計は6 点となる.これより多くの芸術点を得る方法はないため,6 を出力する.
ふたつの料理– 3 / 5
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Two Dishes
入力例2 出力例2
5 7 63
16 73 16
17 73 10
20 73 1
14 73 16
18 73 10
3 73 2
10 73 7
16 73 19
12 73 4
15 73 15
20 73 14
15 73 8
この入力例は小課題1 の制約を満たす.
ふたつの料理– 4 / 5
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Two Dishes
入力例3 出力例3
9 11 99
86 565 58
41 469 -95
73 679 28
91 585 -78
17 513 -63
48 878 -66
66 901 59
72 983 -70
68 1432 11
42 386 -87
36 895 57
100 164 10
96 812 -6
23 961 -66
54 193 51
37 709 82
62 148 -36
28 853 22
15 44 53
77 660 -19
ふたつの料理– 5 / 5