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



可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Candies
飴(Candies)
机の上にN 個の飴が横一列に並んでいる.左からi 番目(1 ≦i ≦N) の飴の美味しさはAi である.
JOI ちゃんは,N 個の飴のうちいくつかを選んで食べることにした.JOI ちゃんは,選んだ飴の美味しさ
の合計を大きくしたい.ただし,普通に選ぶのでは面白くないと思ったJOI ちゃんは,隣り合う2 つの飴
の両方を選ぶことはしないことにした.
JOI ちゃんは,何個の飴を食べるのか,まだ決めていない.JOI ちゃんは,各j (1 ≦j ≦⌈N ⌉) について, 2
j 個の飴を選ぶ場合の美味しさの合計の最大値を知りたい.ここで,⌈x⌉は,x 以上の整数のうち最小のも
のを表す.
課題
机の上にあるN 個の飴の美味しさが与えられたとき,各j (1 ≦j ≦⌈N ⌉) について,j 個の飴を選んだ場 2
合の美味しさの合計の最大値を求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
• 1 行目には,整数N が書かれている.これは机の上にある飴の個数を表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ai が書かれている.これは左からi 番目の飴の美味
しさを表す.
出力
標準出力に⌈N ⌉行で出力せよ.j 行目(1 ≦j ≦⌈N ⌉) には,j 個の飴を選んだ場合の美味しさの合計の最 2 2
大値を出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦200 000.
• 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦N).
飴– 1 / 3
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Candies
小課題
この課題では小課題は全部で2 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [8 点]
• N ≦2 000.
小課題2 [92 点]
追加の制限はない.
入出力例
入力例1 出力例1
5 7
3 12
5 10
1
7
6
入力例1 では,左から順に美味しさが3,5,1,7,6 の飴が並んでいる.以下のように食べるのが最適
である.
• 1 個の飴を食べる場合は,左から4 番目の飴(美味しさ7) を食べる.
• 2 個の飴を食べる場合は,左から2 番目と4 番目の飴(美味しさ5, 7) を食べる.
• 3 個の飴を食べる場合は,左から1 番目と3 番目と5 番目の飴(美味しさ3, 1, 6) を食べる.
隣り合う2 つの飴の両方を選ぶことはできない.例えば,2 個の飴を食べる場合に,左から4 番目と5 番
目の飴(美味しさ7, 6) の両方を食べることはできないことに注意せよ.
飴– 2 / 3
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Candies
入力例2 出力例2
20 936349374
623239331 1855340557
125587558 2763350783
908010226 3622744640
866053126 4439368364
389255266 5243250666
859393857 5982662302
596640443 6605901633
60521559 7183000177
11284043 7309502029
930138174
936349374
810093502
521142682
918991183
743833745
739411636
276010057
577098544
551216812
816623724
飴– 3 / 3