結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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(" "))
  }
}
0