結果

問題 No.572 妖精の演奏
ユーザー YosukeKawadaYosukeKawada
提出日時 2017-12-29 15:19:46
言語 Ruby
(3.2.2)
結果
AC  
実行時間 301 ms / 2,000 ms
コード長 856 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 11,552 KB
実行使用メモリ 16,900 KB
最終ジャッジ日時 2023-08-23 09:00:13
合計ジャッジ時間 4,860 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
15,288 KB
testcase_01 AC 87 ms
15,336 KB
testcase_02 AC 84 ms
15,436 KB
testcase_03 AC 88 ms
15,292 KB
testcase_04 AC 83 ms
15,332 KB
testcase_05 AC 101 ms
15,624 KB
testcase_06 AC 109 ms
15,672 KB
testcase_07 AC 100 ms
15,656 KB
testcase_08 AC 104 ms
15,620 KB
testcase_09 AC 125 ms
15,672 KB
testcase_10 AC 301 ms
16,796 KB
testcase_11 AC 283 ms
16,808 KB
testcase_12 AC 287 ms
16,784 KB
testcase_13 AC 294 ms
16,684 KB
testcase_14 AC 276 ms
16,724 KB
testcase_15 AC 287 ms
16,780 KB
testcase_16 AC 271 ms
16,688 KB
testcase_17 AC 295 ms
16,900 KB
testcase_18 AC 97 ms
15,712 KB
testcase_19 AC 84 ms
15,148 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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