結果

問題 No.572 妖精の演奏
ユーザー YosukeKawadaYosukeKawada
提出日時 2017-12-29 15:19:46
言語 Ruby
(3.3.0)
結果
AC  
実行時間 350 ms / 2,000 ms
コード長 856 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2024-06-01 06:39:27
合計ジャッジ時間 5,167 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 100 ms
12,288 KB
testcase_01 AC 101 ms
12,416 KB
testcase_02 AC 97 ms
12,160 KB
testcase_03 AC 100 ms
12,160 KB
testcase_04 AC 99 ms
12,160 KB
testcase_05 AC 114 ms
12,672 KB
testcase_06 AC 123 ms
12,416 KB
testcase_07 AC 114 ms
12,544 KB
testcase_08 AC 123 ms
12,416 KB
testcase_09 AC 139 ms
12,416 KB
testcase_10 AC 347 ms
12,928 KB
testcase_11 AC 324 ms
12,928 KB
testcase_12 AC 328 ms
13,056 KB
testcase_13 AC 341 ms
13,056 KB
testcase_14 AC 318 ms
12,800 KB
testcase_15 AC 336 ms
12,928 KB
testcase_16 AC 308 ms
12,928 KB
testcase_17 AC 350 ms
12,928 KB
testcase_18 AC 109 ms
12,416 KB
testcase_19 AC 88 ms
12,160 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