結果

問題 No.258 回転寿司(2)
コンテスト
ユーザー くわい
提出日時 2015-09-22 11:29:39
言語 Scala(Beta)
(3.6.2)
結果
AC  
実行時間 1,369 ms / 2,000 ms
コード長 1,303 bytes
コンパイル時間 13,238 ms
コンパイル使用メモリ 263,208 KB
実行使用メモリ 81,868 KB
最終ジャッジ日時 2024-06-29 03:27:34
合計ジャッジ時間 99,851 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 67
権限があれば一括ダウンロードができます

ソースコード

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