結果

問題 No.258 回転寿司(2)
ユーザー siman
提出日時 2021-08-31 11:03:56
言語 Ruby
(3.4.1)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 489 bytes
コンパイル時間 52 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-11-25 04:46:04
合計ジャッジ時間 10,273 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 67
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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