結果

問題 No.258 回転寿司(2)
コンテスト
ユーザー くわい
提出日時 2015-09-22 11:29:39
言語 Scala(Beta)
(3.8.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,303 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,518 ms
コンパイル使用メモリ 289,732 KB
実行使用メモリ 104,108 KB
最終ジャッジ日時 2026-01-25 16:37:03
合計ジャッジ時間 17,287 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 66
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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