結果

問題 No.258 回転寿司(2)
コンテスト
ユーザー siman
提出日時 2021-08-31 11:03:56
言語 Ruby
(4.0.1)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 489 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 282 ms
コンパイル使用メモリ 8,960 KB
実行使用メモリ 15,232 KB
最終ジャッジ日時 2026-01-25 17:05:31
合計ジャッジ時間 19,058 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 67
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

N = gets.to_i
V = gets.split.map(&:to_i)

dp = Array.new(N, 0)
path = Array.new(N, -1)

max_v = 0
start = -1

N.times do |i|
  if dp[i] < V[i]
    dp[i] = V[i]
    path[i] = -1
  end

  (i + 2).upto(N - 1) do |j|
    nv = dp[i] + V[j]
    next if dp[j] >= nv

    dp[j] = nv
    path[j] = i
  end

  if max_v < dp[i]
    max_v = dp[i]
    start = i
  end
end

cur = start
ans = [cur + 1]

while path[cur] != -1
  cur = path[cur]
  ans << cur + 1
end

puts max_v
puts ans.reverse.join(' ')
0