結果

問題 No.572 妖精の演奏
ユーザー YosukeKawada
提出日時 2017-12-29 15:19:46
言語 Ruby
(3.4.1)
結果
AC  
実行時間 348 ms / 2,000 ms
コード長 856 bytes
コンパイル時間 133 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2024-12-21 10:30:31
合計ジャッジ時間 5,092 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def gl
  $stdin.gets.chomp
end

N = gl.to_i
M = gl.to_i

scores = (0...M).map{ gl.split(" ").map{ |a| a.to_i } }
routes = [scores]
(M-1).times { |i|
  route = (0...M).map{ |i|
    (0...M).map{ |j|
      (0...M).map{ |k| routes[-1][i][k] + routes[0][k][j] }.max
    }
  }
  routes << route
}

#routes.each_with_index { |h,i|
#  p i+1
#  h.each{ |r| p r }
#}

N0 = N-1
puts (0..[M,N0].min).map { |d|
  next 0 if d == 1
  (0...M).map { |i|
    if d == 0
      next (0...M).map{ |j| routes[[M,N0].min-1][i][j] }.max
    end

    l = N0 / d
    r = N0 % d
    mid = routes[d-1][i][i] * l
    edge = (0..r).map{ |a|
      b = r - a
      ((0...M).map{ |j| a > 0 ? routes[a-1][j][i] : 0 }.max || 0) + ((0...M).map{ |j| b > 0 ? routes[b-1][i][j] : 0 }.max || 0).tap{ |v|
        #p [mid, v+mid, [d,i,l,r,a,b]]
      }
    }.max
    mid + (edge || 0)
  }.max
}.max
0