← 返回题目列表

AtCoder · joisc2019_e

E. 两道菜

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

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

ふたつの料理 (Two Dishes) - 原题 PDF 第 1 页
原题PDF第1页
ふたつの料理 (Two Dishes) - 原题 PDF 第 2 页
原题PDF第2页
ふたつの料理 (Two Dishes) - 原题 PDF 第 3 页
原题PDF第3页
ふたつの料理 (Two Dishes) - 原题 PDF 第 4 页
原题PDF第4页
ふたつの料理 (Two Dishes) - 原题 PDF 第 5 页
原题PDF第5页
可复制的 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