結果
問題 |
No.572 妖精の演奏
|
ユーザー |
![]() |
提出日時 | 2025-03-20 21:15:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 2,108 bytes |
コンパイル時間 | 239 ms |
コンパイル使用メモリ | 81,844 KB |
実行使用メモリ | 76,684 KB |
最終ジャッジ日時 | 2025-03-20 21:15:42 |
合計ジャッジ時間 | 2,490 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
import sys INF = 1e18 def multiply(A, B, m): B_transposed = [[B[k][j] for k in range(m)] for j in range(m)] res = [[-INF for _ in range(m)] for __ in range(m)] for i in range(m): a_row = A[i] for j in range(m): max_val = -INF b_col = B_transposed[j] for k in range(m): a = a_row[k] if a == -INF: continue b = b_col[k] if b == -INF: continue current = a + b if current > max_val: max_val = current res[i][j] = max_val return res def matrix_power(mat, power, m): result = [[-INF for _ in range(m)] for __ in range(m)] for i in range(m): result[i][i] = 0 current_mat = [row[:] for row in mat] while power > 0: if power % 2 == 1: result = multiply(result, current_mat, m) current_mat = multiply(current_mat, current_mat, m) power = power // 2 return result def vector_mult(v, mat, m): res = [-INF for _ in range(m)] for j in range(m): max_val = -INF for k in range(m): if v[k] == -INF or mat[k][j] == -INF: continue current = v[k] + mat[k][j] if current > max_val: max_val = current res[j] = max_val return res def main(): input = sys.stdin.read().split() ptr = 0 n = int(input[ptr]) ptr += 1 m = int(input[ptr]) ptr += 1 if n == 1: print(0) return A = [] for _ in range(m): row = list(map(int, input[ptr:ptr+m])) ptr += m A.append(row) T = [[-INF for _ in range(m)] for __ in range(m)] for i in range(m): for j in range(m): if i != j: T[i][j] = A[i][j] e = n - 1 M = matrix_power(T, e, m) v0 = [0 for _ in range(m)] v_final = vector_mult(v0, M, m) max_score = max(v_final) print(int(max_score)) if __name__ == "__main__": main()