結果
問題 | No.258 回転寿司(2) |
ユーザー | くわい |
提出日時 | 2015-09-22 11:29:39 |
言語 | Scala(Beta) (3.4.0) |
結果 |
AC
|
実行時間 | 1,448 ms / 2,000 ms |
コード長 | 1,303 bytes |
コンパイル時間 | 11,099 ms |
コンパイル使用メモリ | 264,084 KB |
実行使用メモリ | 80,376 KB |
最終ジャッジ日時 | 2023-09-11 13:09:35 |
合計ジャッジ時間 | 102,653 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,421 ms
80,376 KB |
testcase_01 | AC | 1,334 ms
74,240 KB |
testcase_02 | AC | 1,218 ms
64,588 KB |
testcase_03 | AC | 1,015 ms
63,876 KB |
testcase_04 | AC | 1,198 ms
64,388 KB |
testcase_05 | AC | 1,223 ms
64,652 KB |
testcase_06 | AC | 1,301 ms
68,500 KB |
testcase_07 | AC | 1,100 ms
64,188 KB |
testcase_08 | AC | 1,165 ms
64,328 KB |
testcase_09 | AC | 1,150 ms
64,240 KB |
testcase_10 | AC | 1,037 ms
63,928 KB |
testcase_11 | AC | 1,122 ms
64,160 KB |
testcase_12 | AC | 1,155 ms
64,200 KB |
testcase_13 | AC | 1,111 ms
64,040 KB |
testcase_14 | AC | 1,315 ms
73,552 KB |
testcase_15 | AC | 1,094 ms
64,100 KB |
testcase_16 | AC | 1,109 ms
64,260 KB |
testcase_17 | AC | 1,104 ms
64,520 KB |
testcase_18 | AC | 1,259 ms
68,448 KB |
testcase_19 | AC | 1,070 ms
63,804 KB |
testcase_20 | AC | 1,236 ms
66,492 KB |
testcase_21 | AC | 1,268 ms
68,616 KB |
testcase_22 | AC | 996 ms
63,508 KB |
testcase_23 | AC | 993 ms
63,632 KB |
testcase_24 | AC | 982 ms
63,660 KB |
testcase_25 | AC | 994 ms
63,540 KB |
testcase_26 | AC | 1,279 ms
64,436 KB |
testcase_27 | AC | 1,167 ms
64,288 KB |
testcase_28 | AC | 1,448 ms
76,428 KB |
testcase_29 | AC | 1,187 ms
64,312 KB |
testcase_30 | AC | 1,094 ms
64,060 KB |
testcase_31 | AC | 1,041 ms
64,032 KB |
testcase_32 | AC | 1,143 ms
64,460 KB |
testcase_33 | AC | 1,226 ms
66,408 KB |
testcase_34 | AC | 1,220 ms
64,784 KB |
testcase_35 | AC | 1,218 ms
64,500 KB |
testcase_36 | AC | 1,040 ms
64,176 KB |
testcase_37 | AC | 1,047 ms
64,088 KB |
testcase_38 | AC | 1,120 ms
64,388 KB |
testcase_39 | AC | 1,148 ms
64,208 KB |
testcase_40 | AC | 1,203 ms
64,416 KB |
testcase_41 | AC | 1,251 ms
68,492 KB |
testcase_42 | AC | 1,103 ms
64,400 KB |
testcase_43 | AC | 1,077 ms
64,224 KB |
testcase_44 | AC | 1,269 ms
66,752 KB |
testcase_45 | AC | 1,240 ms
66,576 KB |
testcase_46 | AC | 1,004 ms
63,644 KB |
testcase_47 | AC | 1,215 ms
64,464 KB |
testcase_48 | AC | 1,064 ms
64,104 KB |
testcase_49 | AC | 1,125 ms
64,160 KB |
testcase_50 | AC | 1,013 ms
63,552 KB |
testcase_51 | AC | 1,211 ms
64,404 KB |
testcase_52 | AC | 1,182 ms
64,308 KB |
testcase_53 | AC | 1,039 ms
64,120 KB |
testcase_54 | AC | 1,261 ms
66,496 KB |
testcase_55 | AC | 1,374 ms
71,388 KB |
testcase_56 | AC | 1,224 ms
64,376 KB |
testcase_57 | AC | 1,081 ms
64,020 KB |
testcase_58 | AC | 1,216 ms
64,468 KB |
testcase_59 | AC | 1,307 ms
69,028 KB |
testcase_60 | AC | 1,047 ms
63,984 KB |
testcase_61 | AC | 1,281 ms
66,612 KB |
testcase_62 | AC | 1,131 ms
64,136 KB |
testcase_63 | AC | 1,227 ms
64,672 KB |
testcase_64 | AC | 1,384 ms
78,692 KB |
testcase_65 | AC | 1,223 ms
66,808 KB |
testcase_66 | AC | 1,027 ms
63,936 KB |
testcase_67 | AC | 1,348 ms
74,288 KB |
testcase_68 | AC | 1,251 ms
66,632 KB |
testcase_69 | AC | 1,220 ms
66,576 KB |
testcase_70 | AC | 1,118 ms
64,144 KB |
ソースコード
import java.util.Scanner import scala.collection.mutable object Problem258 { case class State(current: Int, delicious: Int, route: List[Int]) def proc(n: Int, sushi: IndexedSeq[Int]): (Int, List[Int]) = { val DP = mutable.IndexedSeq.fill(n + 2)(State(-1, -1, Nil)) val queue = mutable.Queue[State]() // 開始地点登録 queue.enqueue(State(0, 0, List())) while (queue.nonEmpty) { val s = queue.dequeue() // 最大の美味しさを得られているなら続行 if (DP(s.current).delicious < s.delicious) { DP(s.current) = s // まだ寿司があるなら次へ if (s.current < n) { val getSushi = State(s.current + 2, s.delicious + sushi(s.current), s.current :: s.route) val noGetSushi = State(s.current + 1, s.delicious, s.route) queue.enqueue(getSushi, noGetSushi) } } } // 一番美味しい取り方を返す(1-indexで) val result = DP.maxBy(_.delicious) (result.delicious, result.route.reverse.map(_ + 1)) } def main(args: Array[String]): Unit = { val sc = new Scanner(System.in) val N = sc.nextInt val sushi = IndexedSeq.fill(N)(sc.nextInt) val result = proc(N, sushi) println(result._1) println(result._2.mkString(" ")) } }